백준 1759 암호 만들기

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

📌 해결순서 

1. 백트래킹 dfs 완탐으로 암호를 일단 생성한다

2. 모음 갯수가 자음에 비해서 굉장히 적기 때문에, 모음 알파벳으로만 이루어진 배열을 만든다

3. 암호의 길이가 l 과 같은 경우에, 모음 자음의 갯수가 문제의 조건과 일치 하는지 확인한다

4. 암호의 각 단어가 모음인지 자음인지 판단하고 모음 갯수 >= 1 , 자음 갯수 >= 2 인 경우만 출력한다

 

📌 코드

import sys
input = sys.stdin.readline

l, c = map(int, input().split())
lst = list(map(str, input().split()))
check_lst = ['a', 'e', 'i', 'o', 'u']

lst.sort()
word = []


def dfs(x):
    if len(word) == l:
        # 모음 자음 갯수 체크
        cntMo = 0
        cntJa = 0
        isMo = False
        for char in word:
            for check in check_lst:
                if char == check:
                    isMo = True
                    cntMo += 1
                    break
            if not isMo:
                cntJa += 1
            isMo = False
        # 모음 자음 갯수가 문제 조건을 만족하는 경우에만 출력
        if cntMo >= 1 and cntJa >= 2:
            print(''.join(word))
        return

    for i in range(x, c):
        if lst[i] not in word:
            word.append(lst[i])
            # 한번 사용한 암호는 다시 사용할수 없기 때문에, 탐색할때마다 시작 인덱스를 오른쪽으로 한칸 이동 시킨다
            dfs(i + 1)
            word.pop()


dfs(0)