[백준] 1759 - 암호 만들기 / Python / 골드 5

🚩문제 주소

📄풀이

백트래킹

모든 후보를 다 찾아보려면 너무 비효율적이므로 조건을 걸어서 가지치기를 하는 백트래킹 알고리즘을 활용하여 풀어야 할 것 같았다.

1. 암호는 오름차순으로 정렬이 되어 있다고 하니 입력 받은 알파벳들을 정렬해줍니다.

2. 알파벳 배열을 탐색해야 하는데, 처음부터 끝까지 재귀하면 암호가 조건을 만족하지만 오름차순이 아닌 것들도 포함이 되기 때문에 이미 본 것은 포함하지 않게 인덱스(idx)를 인자로 받아서 재귀할 때 마다 1씩 늘려줍니다.

3. 주어진 암호의 길이와 현재 암호의 길이가 같아지면 자음과 모음의 갯수를 세어서 조건을 만족할 경우 출력한 다음 함수를 종료합니다.

👨‍💻코드

def dfs(length, idx):
  if length == L:
    c_cnt, v_cnt = 0, 0
    for r in result:
      if r in 'aeiou': v_cnt += 1
      else: c_cnt += 1

    if v_cnt >= 1 and c_cnt >= 2:
      print(''.join(result))

    return
  
  for i in range(idx, C):
    if not visited[i]:
      visited[i] = 1
      result.append(alphabet[i])
      dfs(length+1, i+1)
      visited[i] = 0
      result.pop()

L, C = map(int, input().split())
alphabet = input().split()
alphabet.sort()
visited = [0]*C
result = []

dfs(0, 0)