[Baekjoon/Python] 1759번: 암호 만들기(BackTracking)

# Baekjoon 1759번: 암호 만들기

import sys
input = sys.stdin.readline

L, C = map(int, input().split())
code = input().split()
code.sort()

def DFS(cstr, m):
    global L
    
    if m == C:
        if len(cstr) == L:
            count = 0
            flag = False
            for char in cstr:
                if char in 'aeiou':
                    flag = True
                else:
                    count += 1 
            
            if flag == True and 1 < count:
                print(cstr)
        return
    
    DFS(cstr + code[m], m+1)
    DFS(cstr, m+1)
    
DFS("", 0)

이번 문제는 백트래킹 문제이다. 문제에서 요구한 조건은 최소 한 개의 모음과 두 개 이상의 자음을 만족하는 L개의 알파벳 문자를 정렬하여 출력하는 것이다.
모든 경우의 수를 파악하기 위해 DFS 함수를 활용한다. DFS 함수 내부에서 C개의 알파벳을 모두 탐색한 경우(m == C)와 L개의 문자를 구성한 경우(len(cstr) == L)를 만족한 후 자음과 모음이 문제에서 요구한대로 구성되어 있는지 확인하는 과정을 거친다. 이를 만족하는 경우에는 join 함수를 통해 배열을 str로 변환하여 출력하도록 한다.