728x90
문제
테마
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을 활용해 출력한다.
루트 노드까지의 깊이 탐색이 끝나면 다음 이웃 노드의 깊이 탐색으로 넘어가는 백트래킹 방식을 취한다.
'프로그래밍 > programmers&bj' 카테고리의 다른 글
[JAVA] 완주하지 못한 선수 (0) | 2022.02.09 |
---|---|
[Python] 프로그래머스 지형 이동 (0) | 2020.10.30 |
[python] 프로그래머스 삼각 달팽이 (0) | 2020.10.22 |
[python] 프로그래머스 스킬트리 (0) | 2020.10.20 |
[python] 백준 1260번: DFS와 BFS (0) | 2020.10.16 |