[PS] BOJ 1759 / 암호

Minjun Kim

18 Oct 2025 • 4 min read

Thumbnail: Photo by Matt Artz (Unsplash)

문제 링크: https://www.acmicpc.net/problem/1759

백트래킹 문제입니다. 백트래킹을 거쳐 완성한 암호가 답이 될지 안될지를 잘 판단해야 합니다.

풀이

올바른 암호의 조건

문제에서 요구하는 올바른 암호의 조건은 다음과 같습니다.

암호의 길이는 $L$입니다.
암호는 미리 주어진 $C$개의 알파벳으로만 구성됩니다.
암호는 반드시 사전순으로 증가하는 순서로 구성되어야 합니다.
- abc는 올바른 암호이지만, bac는 잘못된 암호입니다.
암호는 반드시 한 개 이상의 모음과 두 개 이상의 자음으로 이루어져야 합니다.
한 개의 알파벳은 암호 내에서 반드시 한 번만 사용됩니다. (중복이 없음)

위 조건을 모두 만족하는 답들을 사전순으로 출력해주면 됩니다.

사전순으로 증가하는 순서로 암호 구성하기

입력으로 주어지는 $C$개의 알파벳은 사전 순으로 주어지지 않습니다. 따라서, 입력받은 알파벳을 정렬해 사전 순으로 만들어야 합니다.

alphabets = input().rstrip().split()
alphabets.sort()

알파벳 정렬하기

이후, 암호를 구성할 때 사전순으로 정렬된 알파벳 배열에서 순서대로 가져오게 되면 만들어진 암호는 언제나 사전순으로 구성됩니다.

추가로, 암호의 각 자리를 채울 때에도 항상 사전 순으로 채워지도록 하려면 이전에 선택한 알파벳보다 사전순으로 뒤에 위치한 알파벳들만 다음 자리에 사용해야 합니다. 이를 위해, 백트래킹에서 암호의 각 자리를 채우는 부분을 다음과 같이 구현했습니다.

def backtracking(depth, start):
    """
    depth: 현재 탐색 깊이 (완성한 암호의 자리 수)
    start: 이번에 채우려는 암호 자리에 사용할 수 있는 알파벳의 최소 인덱스.
    """
    ...
    
    for alpha in range(start, C):
        ...
        backtracking(depth, alpha + 1) # alpha까지의 문자는 다음 자리에 사용 불가

backtracking(0, 0)

답안을 사전순으로 구성하기 위한 백트래킹 구현

알파벳 중복 사용 방지하기

$C$개의 알파벳을 각각 중복 없이 사용해야 하므로, 길이 $C$의 bool 타입 배열을 통해 각 인덱스의 알파벳을 사용했는지 기록해주면 됩니다. 이후, 백트래킹에서 사용하지 않은 알파벳만 암호에 추가하도록 구현해주면 됩니다.

alphabets = input().rstrip().split()
alphabets.sort()
alphabets_used = [False] * C # i번째 원소는 alphabets 배열의 i번째 원소를 암호에 사용했는지의 여부를 나타낸다.

def backtracking(depth, start):
    for alpha in range(start, C):
        if not alphabets_used[alpha]:
            ...

backtracking(0, 0)

알파벳 중복 사용 방지하기

한 개 이상의 모음과 두 개 이상의 자음으로 구성하기

암호를 구성하면서, 자음/모음이 몇 개 사용 되었는지 기록하고 탐색의 깊이가 $L$, 즉 백트래킹을 종료할 시점에 자음이 2개 이상, 모음이 1개 이상 사용되었을 경우에만 답을 출력하면 됩니다.

전체 코드

input = open(0).readline
L, C = map(int, input().split())
alphabets = input().rstrip().split()
alphabets.sort()
alphabets_used = [False] * C
cypher = [""] * L
vowels_cnt = 0
consonants_cnt = 0
vowels = {"a": True, "e": True, "i": True, "o": True, "u": True}

def backtracking(depth, start):
    global vowels_cnt, consonants_cnt
    if depth == L:
        if vowels_cnt >= 1 and consonants_cnt >= 2:
            print("".join(cypher))
        return
    
    for alpha in range(start, C):
        if not alphabets_used[alpha]:
            cypher[depth] = alphabets[alpha]
            alphabets_used[alpha] = True
            if vowels.get(alphabets[alpha], False):
                vowels_cnt += 1
            else:
                consonants_cnt += 1

            backtracking(depth + 1, alpha + 1)

            alphabets_used[alpha] = False
            if vowels.get(alphabets[alpha], False):
                vowels_cnt -= 1
            else:
                consonants_cnt -= 1
    cypher[depth] = ""

backtracking(0, 0)

solution.py