백준 1759 암호 만들기 (Java, DFS)

문제 설명

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

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며, 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어야 합니다.
주어진 C개의 문자들 중에서 L개를 뽑아 사전 순으로 증가하는 순서로 암호를 만들어야 합니다.

---

입력

• 첫째 줄: 정수 L(3 ≤ L ≤ C ≤ 15), C
• 둘째 줄: C개의 알파벳 소문자 (공백으로 구분됨)

---

출력

• 조건을 만족하는 모든 암호를 한 줄에 하나씩 사전 순으로 출력

---

예시 입력

4 6  
a t c i s w

예시 출력

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

---

전체 코드 (Java)

import java.util.*;

public class Main {
    static int L, C;
    static char[] answer, arr;
    static char[] vowel = {'a', 'e', 'i', 'o', 'u'};

    public void DFS(int depth, int start) {
        if (depth == L) {
            int count = 0;
            for (char c : answer) {
                for (char v : vowel) {
                    if (c == v) count++;
                }
            }
            if (count >= 1 && L - count >= 2) {
                for (int i = 0; i < L; i++) System.out.print(answer[i]);
                System.out.println();
            }
            return;
        } else {
            for (int i = start; i < C; i++) {
                answer[depth] = arr[i];
                DFS(depth + 1, i + 1);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        arr = new char[C];
        for (int i = 0; i < C; i++) arr[i] = sc.next().charAt(0);
        Arrays.sort(arr); // 사전 순 출력을 위해 정렬
        answer = new char[C];
        T.DFS(0, 0);
        sc.close();
    }
}

---

코드 설명

1. 정렬

Arrays.sort(arr);

입력받은 문자 배열을 사전 순 출력을 위해 정렬합니다.

---

2. DFS(깊이 우선 탐색)

DFS(int depth, int start)

• depth: 현재까지 고른 문자 수
• start: 다음에 고를 수 있는 문자 인덱스 시작점 (조합 중복 방지용)

---

3. 종료 조건 및 유효성 검사

if (depth == L) {
    // 모음 수 확인 : count
    if (count ≥ 1 && L - count ≥ 2) 출력
}

• L개를 다 골랐으면 조건 검사 후 출력
• L - count로 자음 개수를 계산

---

4. 조합 생성

for (int i = start; i < C; i++) {
    answer[depth] = arr[i];
    DFS(depth + 1, i + 1);
}

• 사전 순 유지를 위해 start부터 시작
• 이미 사용한 문자는 건너뜀

---

시간 복잡도 분석

• 조합의 개수는 C개 중 L개 고르는 경우 → O(c Choose l)
• 각 조합마다 유효성 검사(모음/자음 개수 확인) → O(L × 5) 
• 출력 → O(L) 
• 최대 경우의 수는 15C15 = 1 ~ 15C7 = 6435 수준 → 충분히 완전 탐색 가능

총 시간 복잡도는 O(cCl× L) 수준으로 3 ≤ L ≤ C ≤ 15 이므로 브루트포스 DFS로 풀 수 있습니다.