[백준] 1759 암호 만들기 [Python]

 

풀이 방법

1️⃣ dfs를 통해서 문자를 백트래킹의 과정을 통해 구할 수 있는 모든 문자를 구합니다.

2️⃣ 문자들의 조합 중에서 모음이 최소한 한 개 이상 자음이 최소한 두 개이상이어야 하므로 만들어진 L크기의 문자를 확인합니다.

3️⃣ if문을 통해 정답으로 체크된 문자들이 모여있는 result 리스트를 출력형식에 맞게 출력합니다.

 

 

전체 코드

from sys import stdin as s
s=open('input.txt','rt')

L,C = map(int,s.readline().split())
arr=list(map(str,s.readline().split()))
alpha=['a','e','i','o','u']
arr.sort()
answer=[]
result=[]

def dfs(v, answer):
  #answer의 개수가 L과 같을때 문자체크
  if len(answer) == L:
    #모음개수카운트
    count=0
    #자음개수카운트
    another_count=0
    #answer안에 자음과 모음 몇개있는지 확인
    for i in answer:
        if i in alpha:
            count+=1
        else:
            another_count+=1
    #모음이 1개이상 자음이 2개이상일때만 result에 넣어준다.
    if count>=1 and another_count>=2:
        result.append(answer.copy())
    return
  
  #시작하는 값이 v가 마지막C까지왔으면 return
  if v == C:
    return
  
  #하나씩 넣고 빼면서 백트래킹하는부분
  answer.append(arr[v])
  dfs(v+1, answer)
  answer.pop()
  dfs(v+1, answer)
 
dfs(0, [])

#출력
for i in range(len(result)):
    print(''.join(result[i]))