[BOJ] 암호 만들기

---

코드

from sys import stdin, maxsize
input = stdin.readline

def dfs(start):
    global ans, z, m

    # 탈출조건: 문자열 길이가 L이 되었을 때 리턴
    if len(ans) == L:
        # 조건을 만족하면 정답 출력
        if z >= 2 and m >= 1:
            print(''.join(ans))
        return

    # start 매개변수로 현재 문자 다음의 문자들만 문자열에 추가하게 함
    for i in range(start, C):
        char = charset[i]
        if char not in ans:    # 사용했던 문자는 중복할 수 없음
            # backtracking
            # 자음/모음 개수 추가
            if char in ['a', 'e', 'i', 'o', 'u']:
                m += 1
            else:
                z += 1
            # 문자 추가
            ans.append(char)
            # DFS 수행
            dfs(i)
            # 문자 제거
            ans.pop(-1)
            # 자음/모음 개수 원래대로 돌려놓기
            if char in ['a', 'e', 'i', 'o', 'u']:
                m -= 1
            else:
                z -= 1
    
# input
L, C = map(int, input().split())
charset = list(input().split())

charset.sort()
ans = []    # 만들어진 문자열
z = 0    # 자음개수
m = 0    # 모음개수
dfs(0)

결과

풀이 방법

• N과 M 유형의 문제와 유사한 문제이다. 백트래킹을 활용하는 문제이고 백트래킹은 DFS로 구현하였다.
• 정답에 문자를 추가할 때 자음/모음 개수를 증가시키고, DFS 수행 후 다시 문자를 제거할 때는 자음/모음 개수를 원래대로 돌려놓는다.
• charset에서 현재 방문중인 문자 다음 인덱스의 문자들만 가지고 이후 문자열을 만들어야 하므로 start 매개변수를 사용하였다.

---