[Python] 백준 1759 암호 만들기

1. 문제 - 백준 1759 암호 만들기

https://www.acmicpc.net/problem/1759

 

💡알고리즘 - 백트래킹

• 특정 조건(최소 한 개의 모음, 최소 2개의 자음, c개 문자들 중 길이가 l인 문자열)을 만족하는 집합을 모두 구한다는 점에서
  가지치기 -> 백트래킹을 유추할 수 있다.

l, c = map(int, input().split())
arr = sorted(list(input().split()))
visited = [False] * c

def count_moeum_zaeum(str):   # 최소 한 개의 모음과 2개의 자음으로 구성되어있는지 확인하기 위한 함수
  moeums = ["a", "e", "i", "o", "u"]
  moeum = 0
  zaeum = 0
  
  for s in str:
    if s in moeums:
      moeum += 1
    else:
      zaeum += 1

  return moeum >= 1 and zaeum >= 2

def backtracking(str, idx):
  if count_moeum_zaeum(str) and len(str) == l:   # 조건을 만족하면 출력 후 return한다.
    print(str) 
    return

  for i in range(idx, c):  # idx부터 c까지의 문자열을 순회하며 가능성을 판단하기 위해 이후의 문자를 이어붙여본다.
    if not visited[i]:
      visited[i] = True
      backtracking(str + arr[i], i)
      visited[i] = False
      
    """
    여기서 방문 여부를 복원하는 이유는, 예를들어 문제 예시처럼 a t c i s w 라는 문자열에서 조합을 만든다고 했을 때
    a -> c -> ... 이런 순서로 방문하다가 다른 후보지를 살펴보기 위해 a -> i -> ... 이런순서로 방문할 수 있도록 해야한다.
    방문 여부는 visited로 판단하고 있으므로, visited[i]를 방문하지 않은것으로 복원처리한다. ==> 가지치기
    """

backtracking("", 0)