[python] 백준 1759번: 암호 만들기 (백트래킹)

문제

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

테마

DFS & 백트래킹

 

아이디어

1. 들어온 암호 문자들을 오름차순 정렬한다.

2. DFS 를 통해 l 길이만큼의 암호를 만든다.

3. 길이 l 인 경우이면서 모음이 최소 1개, 자음이 최소 2개인 경우 출력한다.

4. 그렇지 않은 경우 백트래킹을 통해 다음 번 경우의 수를 찾는다.

5. 이를 반복한다.

 

코드

 

from sys import stdin
from copy import deepcopy
l,c = map(int,stdin.readline().split())
alps = list(map(str,stdin.readline().split()))
alps.sort()
moeum = ['a','e','i','o','u']

visited = [0]*c

def DFS(now,cnt,cypher,z,m):
    if cnt == l:
        if z >= 2 and m >= 1:
            print(''.join([str(ch) for ch in cypher]))
    else:
        for i in range(now+1,c):
            if not visited[i]:
                visited[i] = 1
                cy = deepcopy(cypher)
                cy.append(alps[i])
                if alps[i] in moeum:
                    DFS(i,cnt + 1, cy,z,m+1)
                else:
                    DFS(i,cnt + 1, cy, z+1, m)
                visited[i] = 0

DFS(-1,0,[],0,0)

 

설명

 

암호 문자열은 무조건 오름차순이므로, 암호를 선택하는 경우가 5개 중 3개를 고른다 했을 때,

 

[1,2,3,4,5] 에서 [1,4,3] 순으로 고를 수는 없다.

 

그렇기 때문에 경우의 수가 대폭 감소하는데, 이를 DFS 문 else 의 for문에 for i in range(now+1,c) 인 것으로 확인 할 수 있다.

 

만약 현재 고른 문자의 인덱스가 now 일 때, 다음 번 자리에 위치하는 암호 문자는 now + 1 부터 골라야만 한다.

 

만약 now 가 3이고 2가 아직 not visited 이어도, 2를 고르게 되면 오름차순의 조건에 어긋나게 된다.

 

z는 '자음의 수'를 의미하고 m 은 '모음의 수' 를 의미한다.

 

만약 암호 갯수가 l가 동일하면, 완성된 암호가 조건을 만족하는 경우 str.join을 활용해 출력한다.

 

루트 노드까지의 깊이 탐색이 끝나면 다음 이웃 노드의 깊이 탐색으로 넘어가는 백트래킹 방식을 취한다.