[백준(BOJ)] 1759번 암호 만들기

문제

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

1759번: 암호 만들기

두 정수 L, C가 주어진다. 문자의 종류는 C가지가 있고, 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있는 암호를 추측하는 문제다.

예시

Example 1:

Input: 4 6
	a t c i s w
Output: acis
	acit
	aciw
	acst
	acsw
	actw
	aist
	aisw
	aitw
	astw
	cist
	cisw
	citw
	istw

풀이

l, c = map(int, input().split())
alpha = list(input().split())
alpha.sort()

# 모음 자음 개수 확인
def is_ok(password):
    vowels = set('aeiou')
    vowel_count = 0

    for p in password:
        if p in vowels:
            vowel_count += 1

    return vowel_count >= 1 and l - vowel_count >= 2

# 깊이 우선 탐색
def dfs(level, start, path):
    if level == l:
        if is_ok(path):
            print(path)
        return

    for i in range(start, c):
        dfs(level + 1, i + 1, path + alpha[i])

dfs(0, 0, '')

 

- 특정 조건(최소 두 개의 자음, 한 개의 모음)을 만족하는지 확인하는 함수를 사용한다.

- 깊이 우선 탐색을 통해 레벨이 주어진 비밀번호의 길이와 같아지면 조건을 만족하는지 확인하고, 조건을 만족하면 해당 비밀번호를 출력한다.