[DFS/BFS/완전탐색] 1759번 - 암호 만들기(DFS/완전탐색)

[백준] 1759번 - 암호 만들기

C개의 알파벳 목록에서 길이 L인 암호(모음 최소 1개, 자음 최소 2개)를 모두 구하는 것으로 전형적인 완전탐색(백트래킹) 문제다. 풀이 방법은 DFS를 이용하거나 combinations 라이브러리를 이용하는 2가지 방식이 있다. combinations 풀이가 DFS보다 시간측면에서 효율적이기는 했지만 코딩테스트에서 combinations 라이브러리를 사용할 수 없는 경우도 있으므로 1번 풀이로도 풀 수 있어야 한다. 

(풀이1) DFS 이용

풀이 시간: 30분 이내

1) 문제 해결 아이디어

dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수) 를 넘겨주게 했다.

dfs를 호출할 때마다 모음, 자음 개수도 함께 변경하여 넘겨주기 때문에 암호 길이가 L이 되었을 때

굳이 자음, 모음 개수를 다시 셀 필요가 없고 매개변수로 받은 인자 값(v, c)를 활용해 바로 조건에 부합하는지 확인하고 출력하면 된다.

 

첫번째 오류. 틀렸습니다

처음에 탐색 시작 인덱스(idx)를 넘겨주지 않아서 문제가 되었다.

이 문제는 순열이 아닌 조합을 구하는 문제로 가장 최근에 선택한 문자보다 뒤에 있는 알파벳을 골라야 한다!! 그러므로 dfs를 호출할 때 (현재 선택한 알파벳의 인덱스(i) +1 값)으로 넘겨주어야 한다!

 

2) 소스코드

L, C = map(int, input().split())  # 암호 길이, 알파벳목록 길이
graph = list(input().split())  # C개의 문자
graph.sort()  # 오름차순 정렬
password = []  # 가능한 암호

# DFS (암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수)
def dfs(depth, idx, v, c):
  # 암호 길이가 L이 되면
  if depth == L:
    # 모음 1개이상, 자음 2개이상이면
    if v >= 1 and c >= 2:
      print(''.join(password))
    return
  # 암호 길이가 L이 아니면 
  # 탐색 가능한 인덱스부터 알파벳 선택하기
  for i in range(idx, C):
    a = graph[i]  # 선택한 알파벳
    # 선택하지 않은 알파벳이면
    if a not in password:
      # 모음이면
      if a in 'aeiou':
        password.append(a)
        dfs(depth + 1, i + 1, v + 1, c)  # 모음 개수 1개 증가
        password.pop()
      # 자음이면
      else:
        password.append(a)
        dfs(depth + 1, i + 1, v, c + 1)  # 자음 개수 1개 증가
        password.pop()
      
dfs(0, 0, 0, 0)

 

1) 문제 해결 아이디어

dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스) 를 넘겨주게 했다.

암호 길이가 L이 되었을 때 현재 암호(password)의 모음, 자음 개수를 세고 조건에 부합하면 출력시키는 방식이다. 이 방법이 조금 더 코드가 짧고 직관적이어서 이전 방법과 메모리, 시간이 똑같기 때문에 이 방법으로 푸는 걸 더 추천한다. 

 

2) 소스코드

L, C = map(int, input().split())  # 암호 길이, 알파벳목록 길이
graph = list(input().split())  # C개의 문자
graph.sort()  # 오름차순 정렬
password = []  # 가능한 암호

# DFS (암호 길이, 탐색 시작 인덱스)
def dfs(depth, idx):
  # 암호 길이가 L이 되면
  if depth == L:
    v, c = 0, 0  # 모음, 자음 개수
    # 모음, 자음 개수 구하기
    for a in password:
      if a in "aeiou":  v += 1
      else:  c += 1
    # 모음 1개, 자음 2개 이상이면
    if v >= 1 and c >= 2:
      print("".join(password))
    return
  # 암호 길이가 L이 아니면 
  # 탐색 가능한 인덱스부터 알파벳 선택하기
  for i in range(idx, C):
    a = graph[i]  # 선택한 알파벳
    # 선택하지 않은 알파벳이면
    if a not in password:
      password.append(a)
      dfs(depth + 1, i + 1)
      password.pop()
      
dfs(0, 0)

(풀이2) combinations 이용

풀이 시간: 10분 이내

1) 문제 해결 아이디어

combinatons를 이용하여 C개의 문자(graph)에서 L개를 선택한 모든 경우의 수를 얻는다.

각 경우의 수에 대해 모음, 자음 개수를 구하고 조건을 만족할 때에만 암호를 출력시킨다.

 

2) 소스코드

from itertools import combinations

L, C = map(int, input().split())  # 암호 길이, 알파벳목록 길이
graph = list(input().split())  # C개의 문자
graph.sort()  # 오름차순 정렬

# C개의 문자에서 L개 선택(조합)
for p in combinations(graph, L):
  v, c = 0, 0  # 모음, 자음 개수
  # 모음, 자음 개수 구하기
  for a in p:
    if a in "aeiou":  v += 1
    else:  c += 1
  # 모음 1개, 자음 2개 이상이면
  if v >= 1 and c >= 2:
    print("".join(p))