본문 바로가기
알고리즘/백준

[BOJ 백준] 1759 암호만들기 (백트래킹 자바 풀이)

by Renechoi 2025. 5. 25.

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

 

 

 

📌 문제

 

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

 

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

 

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

⚔ 제한 사항

 

 

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

 

출력 

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

 

예시 

 

4 6
a t c i s w

 

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 


 

👀 문제 해석

 

주어진 알파벳들 중에서 특정 조건을 만족하는 모든 가능한 암호의 조합을 찾아내는 문제이다. 암호는 소문자 알파벳 L개로 이루어져 있는데, 크게 네 가지 제약을 갖는다.


첫째, 모든 글자가 서로 달라야 하며 입력으로 주어지는 C개의 후보 문자 집합 안에서만 뽑을 수 있다.

 

둘째, 길이는 정확히 L로 고정되어 있다.

 

셋째, 항상 오름차순(사전순)으로 나열돼 있어야 한다. 예컨대 a c i s는 가능하지만 a s i c는 성립하지 않는다.

 

마지막으로 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음을 포함해야 한다. 이 조건은 암호가 인간이 읽기에도 자연스러워 보이도록 강제하는 일종의 규칙이다.

 


 

🔎 접근

 

시간 복잡도 

 

처음 머릿속에 떠오른 것은 "15개의 알파벳 중 최대 15개까지 골라 나열할 때, 경우의 수는 얼마나 될까?"였다. 순열로 생각하면 단순하게 15!이다. 

 

길이 L의 모든 순열을 만들어 조건을 검사하는 경우를 살펴보면, 

 

경우의 수

  $$
  {}_{C}P_{L}=C\,(C-1)\,(C-2)\dotsm(C-L+1)=\frac{C!}{(C-L)!}
  $$

  최악의 입력은 명세의 상한인 $L=C=15$.

  $$
  {}_{15}P_{15}=15!\;=\;1\,307\,674\,368\,000\ (\approx1.3\text{ 조})
  $$

시간 복잡도
  각 순열을 만들고( O(L) ) + 조건 검사( O(L) ) → O(L) ,
  전체는 $\;O\!\bigl({}_{C}P_{L}\,L\bigr)=O\!\bigl(C! \bigr)$.

 

⇒ 2 초 제한을 절대 통과하지 못한다. 

 

따라서 다음과 같은 질문을 떠올릴 수 있다. 

“모두 나열이 아니라, 필요한 것만 뽑아 볼 순 없을까?”

 

 

곰곰이 문제 조건을 다시 들여다보면 결정적 단서가 숨어 있었다. 암호는 알파벳 순이어야 한다.

 

무슨 의미일까? 예를 들어 글자 a, b, c 가운데 2개 고르는 문제로 단순화시켜 생각해 보자. 

 

글자 a, b, c 중 2개를 골라 만든 순열은 ab ba ac ca bc cb 여섯 가지가 나온다. {a, b}라는 조합에 대해 ab, ba 두 가지가 있을 수 있고, {a, c}는 ac, ca, {b, c}는 bc, cb로 총 6가지 경우가 생긴다.

 

그런데 문제의 조건대로라면 이 중에서 오로지 알파벳 순서대로 나열된 조합만 살아남는다. 즉, ab, ac, bc 단 3가지밖에 안 남는다. 다시 말해, {a, b}, {a, c}, {b, c}라는 글자 묶음(조합) 하나당 단 하나의 순열만 의미가 있다는 이야기다. 다른 순서들은 고려할 가치가 없다.

 

다시 말해 ‘누구를 골랐느냐’(조합)만 같다면 ‘어떻게 배열했느냐’(순열)는 이미 결정돼 있다.

 

 

“알파벳 순” 조건이 순열의 5/6을 쓰레기통에 곧장 던져 버린다. 그렇다면 굳이 버려질 5개를 생성할 이유가 없다. 문제는 순열이 아니라 “글자 묶음(조합)을 어떻게 고르느냐”로 축소된다.

 

이랬을 때, 경우의 수와 시간 복잡도는 어떻게 변할까? 

 

경우의 수는 최대

$$

\binom{C}{L}

$$

이고, $C=15$일 때 가장 많은 조합이 나오는 구간이 $L=7$ 또는 $8$이다.

 

이를 계산하면, $\displaystyle\binom{15}{7}=6 435$ 개가 최대 수이다. 

 

결국, 이 문제는 "순서를 따지는 순열 문제에서 순서를 무시한 조합 문제로 변신한 셈"이다. 같은 알파벳을 골랐다면 무조건 하나의 암호밖에 만들어지지 않으므로, 사실상 알파벳을 선택하는 것만 중요하지, 배열하는 것은 중요하지 않게 된다. 그 결과 전체 경우의 수는 급격히 줄어들어, 최악의 경우에도 단지 수천 개 정도의 조합만 생각하면 충분해졌다.

 

어떻게 설계할 것인가? 

이제 n개 중 r개를 뽑는 조합 문제가 되었으므로, 세부 조건들을 고려한 풀이 설계를 해보자. 

 

이 문제에는 단순한 조합 외에 두 가지의 추가적인 조건이 붙어 있다.

  • 최소 1개의 모음을 포함해야 한다.
  • 최소 2개의 자음을 포함해야 한다.

이 조건을 만족시키면서도, 알파벳이 반드시 오름차순으로 나열된 조합만 생성해야 한다.

 

조합을 미리 완성시킨 뒤, 모음·자음을 세서 떨어뜨리는 후처리 방식이 가능할 것이다. 하지만 백트래킹을 사용한다면, 탐색 과정에서 불필요한 갈래를 아예 생성하지 않는 프루닝이 가능할 것이다. 

 

  • 뼈대 프로세스:
    1. 글자를 한 개 고른다.
    2. 고른 글자 뒤쪽에서 또 한 개 고른다.
    3. 이렇게 L 개를 모으면 “암호 후보”가 완성된다.
    4. 모으는 중에 “이 길은 틀렸어!”가 보이면 즉시 뒤로(Back) 돌아가서(Track) 다른 길을 탐색한다.
  • 결과:
    • 글자들이 원래 정렬 순서(a가 t보다 앞서면 암호에서도 a가 t보다 앞)로만 쌓이므로 같은 알파벳끼리 순서를 바꾸는 불필요한 경우가 자연히 사라진다.
    • 그래서 완전 탐색(순열)보다 가지 수가 훨씬 적다.

알고리즘을 시작하기 전에 먼저 입력 알파벳을 오름차순으로 정렬해 두는 것도 필요하다. 이렇게 하면 깊이-우선 탐색(DFS)이 진행되는 순서가 곧 사전 순 출력이 되므로, 완성된 암호를 따로 정렬하거나 버퍼에 모아 두었다가 다시 정렬할 필요가 없다.

 

함수는 다음과 같이 모델링할 수 있다. 

 

세 개의 인자를 갖는 탐색 함수 dfs이다. 

  1. 현재 시작 인덱스(다음에 고려할 알파벳의 위치),
  2. 지금까지 선택한 글자들,
  3. 그리고 모음 개수(자음 개수는 선택 길이 - 모음으로 구할 수 있다).

이렇게 세 가지 정보만 있으면 조건 검사가 한 줄로 끝난다.

“남은 칸이 L - 현재길이인데, 자음이 최소 2개 모자라면?”
→ 더 내려갈 가치가 없으니 즉시 return.

 

함수 dfs( start, depth, 모음카운트 ):
    # ① 길이 L에 도달 ―–– 출력 & 종료
    만약 depth == L:
        자음카운트 ← L - 모음카운트
        만약 모음과 자음 조건 부합 :
			현재까지 쌓인 글자 그대로 출력
        return                   # 기저 조건

    # ② 아직 길이가 모자라면, 남은 알파벳을 하나씩 선택
    반복 i ← start .. C-1:
        알파벳 ← 가능한알파벳들[i]

        # 다음 호출에 전달할 모음 개수 계산
        다음모음카운트 ← 모음카운트 + (알파벳 ∈ 모음 ? 1 : 0)

        # 재귀: i+1부터 살펴야 사전순이 유지됨
        dfs( start = i + 1, depth = depth + 1, 모음카운트 = 다음모음카운트 )

        # 선택 취소 (backtracking)
        
        
// 호출시 
dfs( start = 0, depth = 0, 모음카운트 = 0 )

 

 


 

💡 풀이 코드

 

이제 앞서 정리한 DFS-백트래킹 아이디어를 자바로 구현해보자. 


가능한알파벳들을 정렬해서 저장하고, dfs가 사전순으로 가지를 뻗도록 만든 것이 핵심이다.

 

🔖 코드 준비 및 입력 받기

우선, 백준 포맷에 따라 입력을 받아야 한다. 문제에서 주어진 입력을 예시로 살펴보면,  

4 6
a t c i s w

 

여기서 L = 4, C = 6이며, 사용 가능한 알파벳은 {a, t, c, i, s, w}이다. 

 

초기화 및 입력 과정에서 이 문자는 배열에 저장된 후 정렬된다. 따라서 실제 데이터는 다음과 같이 준비된다.

 

입력 알파벳 a t c i s w
정렬 후 a c i s t w

 

이제 실제 코드의 입력 처리 부분을 살펴보면,

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
L = Integer.parseInt(stringTokenizer.nextToken());  // 암호 길이 L = 4
C = Integer.parseInt(stringTokenizer.nextToken());  // 후보 알파벳 수 C = 6
가능한알파벳들 = new char[C];

stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < C; i++) {
    가능한알파벳들[i] = stringTokenizer.nextToken().charAt(0);
}

// 정렬 후: 가능한알파벳들 = ['a','c','i','s','t','w']
Arrays.sort(가능한알파벳들);

 

이렇게 하여 이제 입력 데이터 처리는 끝났다. 

 

 

🚩 DFS 재귀 호출 메커니즘 

재귀호출 한 번마다

  1. 현재 깊이(depth)와 모음 – 자음 카운트를 확인,
  2. 조건에 어긋나면 즉시 리턴(프루닝),
  3. 다음 알파벳을 선택하며 **start = i + 1**로 인덱스를 넘겨서
    이미 사용한 글자를 다시 보지 않도록 한다.

DFS 함수 호출이 처음 실행될 때의 상황은 

  • start = 0, depth = 0, 모음카운트 = 0, 암호를 만들기 시작한다.
  • 현재 스택(sb)은 비어 있습다.

여기서부터 DFS를 통해 조합을 만들어 나간다. 

 

graph TD
start((DFS start=0, depth=0, 모음=0, sb="")) --> A["a (모음+1)"]
start --> C["c (모음+0)"]
start --> I["i (모음+1)"]
start --> S["s (모음+0)"]
start --> T["t (모음+0)"]
start --> W["w (모음+0)"]

A --> AC["ac (모음=1)"]
A --> AI["ai (모음=2)"]
A --> AS["as (모음=1)"]
A --> AT["at (모음=1)"]
A --> AW["aw (모음=1)"]

AC --> ACI["aci (모음=2)"]
AC --> ACS["acs (모음=1)"]
...

 

예를 들어, acis가 출력되는 데이터 흐름을 살펴보면,

  • DFS(0,0,0) → a 선택 → 모음 1개
  • DFS(1,1,1) → c 선택 → 모음 그대로 1개
  • DFS(2,2,1) → i 선택 → 모음 2개로 증가
  • DFS(3,3,2) → s 선택 → 모음 그대로 2개 (자음도 2개)

이제 길이 4(L)에 도달했으므로 조건 확인:

  • 모음 2개, 자음 2개 → 조건 충족
  • 따라서 현재 스택(sb)인 "acis" 출력

백트래킹으로 돌아가 다른 조합도 계속 탐색을 진행한다.

 

이렇게 계속 깊이를 늘려가며 조합을 생성한다. 

 

코드는 다음과 같다. 

public static void dfs(int start, int depth, int 모음카운트) {
    if (depth == L) {
        int 자음카운트 = L - 모음카운트;
        if (모음카운트 >= 1 && 자음카운트 >= 2) {
            System.out.println(sb.toString());  // 완성된 암호 출력
        }
        return;  // 기저 조건
    }

    for (int i = start; i < C; i++) {
        char 알파벳 = 가능한알파벳들[i];
        sb.append(알파벳);  // 알파벳 추가

        dfs(i + 1, depth + 1, 모음개수계산(모음카운트, 알파벳));  // 재귀 호출

        sb.deleteCharAt(sb.length() - 1);  // 백트래킹: 추가한 알파벳 제거
    }
}

private static int 모음개수계산(int 모음카운트, char 알파벳) {
    return 모음카운트 + (모음.contains(알파벳) ? 1 : 0);
}

 

  • DFS는 항상 정렬된 순서대로 진행된다.
  • 각 재귀 호출은 새로운 알파벳을 추가하고, 조건을 검사하여 출력하거나 백트래킹으로 돌아간다.

최종적으로 이 DFS가 완성하는 암호 조합은 예시 입력에 대해 다음과 같은 출력 결과를 생성한다.

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

 

⁉️ 그런데 이 코드는 충분하지 않다. 

 

위와 같은 방식으로 정답을 통과한다. 

 

 

그런데 이 코드만으로는 충분하지 않다. 왜일까? 

 

“조건 불충족”인 가지를 끝까지 파보는 낭비 때문이다. 

 

단순 DFS는 깊이 = L에 도달하기 전에는 모음·자음 개수를 확정하지 않는다.

 

즉, 이것이 앞서 언급한 pruning을 하지 않은 케이스,  이미 L 길이까지 탐색한 후에 모음과 자음 조건을 확인하여 탈락시키는 후처리 방식이다. 따라서, L 길이를 만들기도 전에 이미 조건을 만족할 가능성이 전혀 없는 탐색 경로조차 끝까지 완성해버리는 비효율성이 발생한다.

 

예컨대 L = 4인데 현재까지 모음이 0개, 자음이 2개라면 남은 칸은 두 칸뿐이다. 규칙상 모음은 최소 한 개, 자음은 최소 두 개여야 하므로 앞으로 채울 수 있는 최대 모음이 두 개이기 때문에 이 경우는 아직 희망이 있다.

 

그런데 모음 3개 · 자음 0개처럼 남은 칸이 1인데 자음을 2개나 더 넣어야 하는 상태도 전부 내려가 본 뒤에야 “아, 안 되네”라며 돌아온다. 즉, 이런 경우에는 더 이상 탐색을 진행할 이유가 없고 즉시 리턴해야 하는데, 이전의 코드는 그것까지 끝까지 탐색한다. 결과적으로 상당히 많은 무의미한 호출이 발생하는 것이다.

 

<svg viewBox="0 0 1200 500" xmlns="http://www.w3.org/2000/svg">
  <!-- 배경 -->
  <rect width="1200" height="500" fill="#f8f9fa"/>
  
  <!-- 제목 -->
  <text x="600" y="30" text-anchor="middle" font-family="Arial, sans-serif" font-size="18" font-weight="bold" fill="#333">
    DFS 백트래킹에서 Pruning 없이 발생하는 비효율성
  </text>
  
  <!-- 조건 표시 -->
  <rect x="20" y="50" width="300" height="60" fill="#e3f2fd" stroke="#1976d2" stroke-width="2" rx="5"/>
  <text x="170" y="70" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" font-weight="bold" fill="#1976d2">
    조건: L=4, 모음≥1, 자음≥2
  </text>
  <text x="170" y="90" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" fill="#1976d2">
    가능한 알파벳: a, c, i, s, t, w
  </text>
  
  <!-- 효율적인 경로 (왼쪽) -->
  <text x="200" y="140" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" font-weight="bold" fill="#2e7d32">
    ✓ 효율적인 경로 (조건 만족 가능)
  </text>
  
  <!-- 루트 노드 -->
  <circle cx="200" cy="170" r="15" fill="#4caf50" stroke="#2e7d32" stroke-width="2"/>
  <text x="200" y="175" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" fill="white" font-weight="bold">시작</text>
  
  <!-- Level 1 - 효율적 경로 -->
  <circle cx="150" cy="220" r="12" fill="#66bb6a" stroke="#2e7d32" stroke-width="2"/>
  <text x="150" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">a</text>
  <text x="150" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">모음:1</text>
  
  <circle cx="250" cy="220" r="12" fill="#81c784" stroke="#2e7d32" stroke-width="2"/>
  <text x="250" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">c</text>
  <text x="250" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">자음:1</text>
  
  <!-- Level 2 - 효율적 경로 -->
  <circle cx="130" cy="270" r="12" fill="#66bb6a" stroke="#2e7d32" stroke-width="2"/>
  <text x="130" y="274" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">c</text>
  <text x="130" y="290" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">모음:1,자음:1</text>
  
  <circle cx="170" cy="270" r="12" fill="#66bb6a" stroke="#2e7d32" stroke-width="2"/>
  <text x="170" y="274" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">i</text>
  <text x="170" y="290" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">모음:2</text>
  
  <!-- Level 3 - 효율적 경로 -->
  <circle cx="110" cy="320" r="12" fill="#66bb6a" stroke="#2e7d32" stroke-width="2"/>
  <text x="110" y="324" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">i</text>
  <text x="110" y="340" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">모음:2,자음:1</text>
  
  <circle cx="150" cy="320" r="12" fill="#66bb6a" stroke="#2e7d32" stroke-width="2"/>
  <text x="150" y="324" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">s</text>
  <text x="150" y="340" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#2e7d32">모음:2,자음:2</text>
  
  <!-- Level 4 - 성공 -->
  <circle cx="90" cy="370" r="12" fill="#2e7d32" stroke="#1b5e20" stroke-width="2"/>
  <text x="90" y="374" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">s</text>
  <text x="90" y="390" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#1b5e20">✓ acis</text>
  
  <circle cx="130" cy="370" r="12" fill="#2e7d32" stroke="#1b5e20" stroke-width="2"/>
  <text x="130" y="374" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">t</text>
  <text x="130" y="390" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#1b5e20">✓ acit</text>
  
  <!-- 연결선 - 효율적 경로 -->
  <line x1="200" y1="185" x2="150" y2="205" stroke="#2e7d32" stroke-width="2"/>
  <line x1="200" y1="185" x2="250" y2="205" stroke="#2e7d32" stroke-width="2"/>
  <line x1="150" y1="235" x2="130" y2="255" stroke="#2e7d32" stroke-width="2"/>
  <line x1="150" y1="235" x2="170" y2="255" stroke="#2e7d32" stroke-width="2"/>
  <line x1="130" y1="285" x2="110" y2="305" stroke="#2e7d32" stroke-width="2"/>
  <line x1="130" y1="285" x2="150" y2="305" stroke="#2e7d32" stroke-width="2"/>
  <line x1="110" y1="335" x2="90" y2="355" stroke="#2e7d32" stroke-width="2"/>
  <line x1="110" y1="335" x2="130" y2="355" stroke="#2e7d32" stroke-width="2"/>
  
  <!-- 구분선 -->
  <line x1="400" y1="120" x2="400" y2="750" stroke="#666" stroke-width="2" stroke-dasharray="5,5" opacity="0.5"/>
  
  <!-- 비효율적인 경로 (오른쪽) -->
  <text x="800" y="140" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" font-weight="bold" fill="#d32f2f">
    ✗ 비효율적인 경로 (Pruning 없음)
  </text>
  
  <!-- 루트 노드 -->
  <circle cx="800" cy="170" r="15" fill="#f44336" stroke="#d32f2f" stroke-width="2"/>
  <text x="800" y="175" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" fill="white" font-weight="bold">시작</text>
  
  <!-- Level 1 - 비효율적 경로 -->
  <circle cx="680" cy="220" r="12" fill="#ef5350" stroke="#d32f2f" stroke-width="2"/>
  <text x="680" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">c</text>
  <text x="680" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:1</text>
  
  <circle cx="750" cy="220" r="12" fill="#ef5350" stroke="#d32f2f" stroke-width="2"/>
  <text x="750" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">s</text>
  <text x="750" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:1</text>
  
  <circle cx="850" cy="220" r="12" fill="#ef5350" stroke="#d32f2f" stroke-width="2"/>
  <text x="850" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">t</text>
  <text x="850" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:1</text>
  
  <circle cx="920" cy="220" r="12" fill="#ef5350" stroke="#d32f2f" stroke-width="2"/>
  <text x="920" y="224" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">w</text>
  <text x="920" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:1</text>
  
  <!-- Level 2 - 문제 상황 -->
  <circle cx="660" cy="270" r="12" fill="#ff7043" stroke="#d32f2f" stroke-width="2"/>
  <text x="660" y="274" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">s</text>
  <text x="660" y="290" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:2</text>
  
  <circle cx="700" cy="270" r="12" fill="#ff7043" stroke="#d32f2f" stroke-width="2"/>
  <text x="700" y="274" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">t</text>
  <text x="700" y="290" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:2</text>
  
  <circle cx="740" cy="270" r="12" fill="#ff7043" stroke="#d32f2f" stroke-width="2"/>
  <text x="740" y="274" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">w</text>
  <text x="740" y="290" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:2</text>
  
  <!-- Level 3 - 희망 없는 상황 -->
  <circle cx="640" cy="320" r="12" fill="#ff8a65" stroke="#d32f2f" stroke-width="2"/>
  <text x="640" y="324" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">t</text>
  <text x="640" y="340" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:3</text>
  
  <circle cx="680" cy="320" r="12" fill="#ff8a65" stroke="#d32f2f" stroke-width="2"/>
  <text x="680" y="324" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">w</text>
  <text x="680" y="340" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#d32f2f">자음:3</text>
  
  <!-- Level 4 - 실패 -->
  <circle cx="620" cy="370" r="12" fill="#d32f2f" stroke="#b71c1c" stroke-width="2"/>
  <text x="620" y="374" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">w</text>
  <text x="620" y="390" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#b71c1c">✗ cstw</text>
  <text x="620" y="405" text-anchor="middle" font-family="Arial, sans-serif" font-size="7" fill="#b71c1c">모음:0</text>
  
  <circle cx="660" cy="370" r="12" fill="#d32f2f" stroke="#b71c1c" stroke-width="2"/>
  <text x="660" y="374" text-anchor="middle" font-family="Arial, sans-serif" font-size="9" fill="white">w</text>
  <text x="660" y="390" text-anchor="middle" font-family="Arial, sans-serif" font-size="8" fill="#b71c1c">✗ ctww</text>
  <text x="660" y="405" text-anchor="middle" font-family="Arial, sans-serif" font-size="7" fill="#b71c1c">모음:0</text>
  
  <!-- 연결선 - 비효율적 경로 -->
  <line x1="800" y1="185" x2="680" y2="205" stroke="#d32f2f" stroke-width="2"/>
  <line x1="800" y1="185" x2="750" y2="205" stroke="#d32f2f" stroke-width="2"/>
  <line x1="800" y1="185" x2="850" y2="205" stroke="#d32f2f" stroke-width="2"/>
  <line x1="800" y1="185" x2="920" y2="205" stroke="#d32f2f" stroke-width="2"/>
  <line x1="680" y1="235" x2="660" y2="255" stroke="#d32f2f" stroke-width="2"/>
  <line x1="680" y1="235" x2="700" y2="255" stroke="#d32f2f" stroke-width="2"/>
  <line x1="680" y1="235" x2="740" y2="255" stroke="#d32f2f" stroke-width="2"/>
  <line x1="660" y1="285" x2="640" y2="305" stroke="#d32f2f" stroke-width="2"/>
  <line x1="660" y1="285" x2="680" y2="305" stroke="#d32f2f" stroke-width="2"/>
  <line x1="640" y1="335" x2="620" y2="355" stroke="#d32f2f" stroke-width="2"/>
  <line x1="640" y1="335" x2="660" y2="355" stroke="#d32f2f" stroke-width="2"/>
  
  <!-- 문제점 표시 화살표와 설명 -->
  <path d="M 580 320 Q 560 340 540 360" stroke="#ff5722" stroke-width="3" fill="none" marker-end="url(#arrowhead)"/>
  <text x="500" y="350" font-family="Arial, sans-serif" font-size="12" font-weight="bold" fill="#ff5722">
    이미 자음 3개!
  </text>
  <text x="500" y="365" font-family="Arial, sans-serif" font-size="10" fill="#ff5722">
    모음 0개, 남은 칸 1개
  </text>
  <text x="500" y="380" font-family="Arial, sans-serif" font-size="10" fill="#ff5722">
    → 조건 만족 불가능
  </text>
  
  <!-- 화살표 마커 정의 -->
  <defs>
    <marker id="arrowhead" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#ff5722"/>
    </marker>
  </defs>
  
  
</svg>

 

 

이러한 비효율성을 없애기 위해, 다음과 같은 프루닝 로직을 추가할 수 있다.

 

DFS 함수에 아래 코드를 삽입해서,

int 남은칸 = L - depth;
int 최소필요모음 = Math.max(0, 1 - 모음카운트);
int 최소필요자음 = Math.max(0, 2 - (depth - 모음카운트));
if (남은칸 < 최소필요모음 + 최소필요자음) {
    return; // 조기 종료 (가지치기)
}

 

다음과 같은 논리로 조기 종료를 수행한다.

  • 남은 칸 수가 현재 모자란 최소한의 모음과 자음 수를 채우기에 부족하다면, 즉시 탐색을 멈춘다.
  • 최소필요모음은 1개에서 현재까지의 모음 수를 뺀 값이다.
  • 최소필요자음은 2개에서 현재까지의 자음 수를 뺀 값이다.
  • 위 두 가지를 더한 값이 현재 남아있는 칸보다 크다면, 무조건 조건을 충족할 수 없으므로 이 경로는 더 이상 볼 필요가 없다.

이때, 코드에 등장한 로직을 다시 한 번 보면, 

int 최소필요모음 = Math.max(0, 1 - 모음카운트);
int 최소필요자음 = Math.max(0, 2 - (depth - 모음카운트));

 

이 로직은 다음과 같은 의미이다.

  • 암호는 최소 모음 1개, 자음 2개를 가져야 한다.
  • 지금까지 선택한 알파벳 중 모음이 이미 1개 이상 있으면, 추가로 필수 모음은 없으므로 0이 된다.
  • 하지만, 현재 모음이 전혀 없다면 적어도 1개의 모음이 더 필요하므로, 1 - 모음카운트가 최소필요모음이다.
  • 자음의 경우도 비슷하게, 이미 자음이 2개 이상 있다면 추가로 필수 자음은 없다.
  • 현재까지 선택된 자음은 depth - 모음카운트이므로, 자음이 모자라다면 그만큼 자음이 더 필요하다.

예를 들어 현재 상태가 다음과 같다고 하자.

  • 암호 길이 L = 4
  • 현재 선택된 글자: {t, s, w} (모음 0개, 자음 3개)
  • 현재 depth = 3 (남은 칸은 1개)

이때 필요한 최소 모음은 아직 1개도 없으므로 1개이다. 필요한 자음은 이미 3개가 선택되었으므로 더 이상 필요 없으므로 0개이다.

남은칸 = 1
최소필요모음 = 1
최소필요자음 = 0

 

남은칸(1) ≥ 최소필요모음+최소필요자음(1)이므로 가능성은 아직 있다. 즉, 다음 글자가 반드시 모음이어야 한다는 것이다. 하지만 다음과 같은 케이스는 어떨까?

 

예를 들어, “모음만 가득 뽑아 놓고 더 이상 자음을 넣을 자리가 없을 때”다.


길이 L = 4인 상황에서, 

 

현재까지 선택 depth 모은 cnt 자음 cnt 남은 칸 최소필요모음 최소필요자음 남은칸 < 필요합계?
a i o 3 3 0 1 0 2 1 < 2 → true

 

int 남은칸 = 4 - 3;                      // 1
int 최소필요모음 = Math.max(0, 1 - 3);   // 0
int 최소필요자음 = Math.max(0, 2 - 0);   // 2

 

남은칸(1) < 최소필요모음+최소필요자음(2)가 성립하므로, return; 이 실행되고 aio‧‧로 시작하는 모든 하위 가지가 통째로 잘린다.

 

덕분에 “어차피 실패”가 확정된 가지를 확장하거나 스택에 쌓는 일을 미연에 방지하게 된다.

 

이러한 프루닝을 수행하는 조건을 판단하는 함수를 별도로 만들어서 처리한다면, 이를 유망함수(promising function) 라고 한다.

 

유망함수는 지금 탐색 중인 노드(상태)가 앞으로 탐색을 계속 진행할 가치가 있는지를 결정하는 역할을 한다. 즉, 위 코드에서 작성한 아래 조건 부분이 바로 유망함수의 역할을 수행하는 부분이라고 할 수 있다.

 

// 유망함수(promising function)의 역할을 하는 부분
private static boolean isPromising(int depth, int 모음카운트) {
    int 남은칸 = L - depth;
    int 최소필요모음 = Math.max(0, 1 - 모음카운트);
    int 최소필요자음 = Math.max(0, 2 - (depth - 모음카운트));
    
    return 남은칸 >= (최소필요모음 + 최소필요자음);
}

 

 

DFS 내부에서 다음과 같이 사용될 것이다.

if (!isPromising(depth, 모음카운트)) {
    return;  // 조기 종료 (가지치기)
}

 

이제 다시 본래 코드로 돌아와서, 가지치기를 적용한 최종적인 DFS 함수는 다음과 같다.

 

public static void dfs(int start, int depth, int 모음카운트) {
		if (!isPromising(depth, 모음카운트)) {
            return;  
        }

		if (depth == L) {
			System.out.println(sb);
			return;
		}

		for (int i = start; i < C; i++) {
			char 알파벳 = 가능한알파벳들[i];
			sb.append(알파벳);
			dfs(i + 1, depth + 1, 모음개수계산(모음카운트, 알파벳));
			sb.deleteCharAt(sb.length() - 1);
		}
	}

	private static int 모음개수계산(int 모음카운트, char 알파벳) {
		return 모음카운트 + (모음.contains(알파벳) ? 1 : 0);
	}
    
    private static boolean isPromising(int depth, int 모음카운트) {
        int 남은칸 = L - depth;
        int 최소필요모음 = Math.max(0, 1 - 모음카운트);
        int 최소필요자음 = Math.max(0, 2 - (depth - 모음카운트));
    
        return 남은칸 >= (최소필요모음 + 최소필요자음);
    }

 


 

🚀 최종 제출 코드 

 

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static int L;
	static int C;
	static char[] 가능한알파벳들;
	static final Set<Character> 모음 = Set.of('a', 'e', 'i', 'o', 'u');
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		L = parseInt(stringTokenizer.nextToken());
		C = parseInt(stringTokenizer.nextToken());
		가능한알파벳들 = new char[C];

		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 0; i < C; i++) {
			가능한알파벳들[i] = stringTokenizer.nextToken().charAt(0);
		}
		Arrays.sort(가능한알파벳들);

		dfs(0, 0, 0);
	}

    public static void dfs(int start, int depth, int 모음카운트) {
		if (!isPromising(depth, 모음카운트)) {
            return;  
        }

		if (depth == L) {
			System.out.println(sb);
			return;
		}

		for (int i = start; i < C; i++) {
			char 알파벳 = 가능한알파벳들[i];
			sb.append(알파벳);
			dfs(i + 1, depth + 1, 모음개수계산(모음카운트, 알파벳));
			sb.deleteCharAt(sb.length() - 1);
		}
	}

	private static int 모음개수계산(int 모음카운트, char 알파벳) {
		return 모음카운트 + (모음.contains(알파벳) ? 1 : 0);
	}
    
    private static boolean isPromising(int depth, int 모음카운트) {
        int 남은칸 = L - depth;
        int 최소필요모음 = Math.max(0, 1 - 모음카운트);
        int 최소필요자음 = Math.max(0, 2 - (depth - 모음카운트));
    
        return 남은칸 >= (최소필요모음 + 최소필요자음);
    }

}

 

 

 

반응형