[BOJ/Back-Tracking] 백준 1759 - 암호 만들기 (Java)

1759 - 암호 만들기

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

문제

암호는 서로 다른 L개의 알파벳 소문자/ 최소 1개의 모음(a, e, i, o, u) + 최소 2개의 자음으로 구성
암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열
암호로 사용했을 법한 문자의 종류는 C가지
=> C개의 문자 모두 주어졌을 때, 가능성 있는 암호들 모두 구하기

입력
첫째 줄: 두 정수 L, C (3 <= L <= C <= 15)
다음 줄: C개의 문자 공백 구분 (중복 X)
출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호 모두 출력

---

풀이

DFS + Backtracking

모음 검사

static boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

 

• `depth == L`: 모음 1개 이상 + 자음 2개 이상
• 지금 선택한 문자 
  • 모음 O -> `vowel` 카운트 + 1
  • 자음 -> `consonant`  카운트 + 1

static void dfs(int start, int depth, int vowel, int consonant) {
    if (depth == L) {
        if (vowel >= 1 && consonant >= 2) {
            sb.append(pwd).append('\n');
        }
        return;
    }

    for (int i = start; i < C; i++) {
        char ch = arr[i];
        pwd[depth] = ch;

        if (isVowel(ch)) dfs(i + 1, depth + 1, vowel + 1, consonant);
        else dfs(i + 1, depth + 1, vowel, consonant + 1);
    }
}

---

코드

import java.io.*;
import java.util.*;

// 암호 만들기
public class boj_1759 {
    static int L, C;
    static char[] arr;
    static char[] pwd;
    static StringBuilder sb = new StringBuilder();

    static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    static void dfs(int start, int depth, int vowel, int consonant) {
        if (depth == L) {
            if (vowel >= 1 && consonant >= 2) {
                sb.append(pwd).append('\n');
            }
            return;
        }

        for (int i = start; i < C; i++) {
            char ch = arr[i];
            pwd[depth] = ch;

            if (isVowel(ch)) dfs(i + 1, depth + 1, vowel + 1, consonant);
            else dfs(i + 1, depth + 1, vowel, consonant + 1);
        }
    }

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

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        pwd = new char[L];
        arr = new char[C];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken().charAt(0);
        }

        Arrays.sort(arr);

        dfs(0, 0, 0, 0);

        System.out.println(sb);
    }
}