백준 1759 암호 만들기 (Gold5)

정답코드

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

public class Main {
	static int L,C;
    static char[] alpha;
    static boolean[] visited;
    static ArrayList<String> result = new ArrayList<String>();

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

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

        alpha = new char[C];
        st = new StringTokenizer(bf.readLine());

        for(int i = 0; i<C; i++) {
            alpha[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(alpha);
        visited = new boolean[C];

        DFS(0,0);
    }

    public static void DFS(int idx, int depth){
        //비밀번호 길이 만큼 만들었으면 종료조건
        if (depth == L){
            String result = "";
            for (int i = 0; i<C; i++){
                if (visited[i]){
                    result+=alpha[i];
                }
            }
            //유효한 비밀번호일 때
            if(validCheck(result)){
                System.out.println(result);
            }
        }
		
        //지금 알파벳이 포함될 때와 포함되지 않을 때 구분해서 DFS를 돌림
        for(int i = idx; i < C; i++){
            visited[i] = true;
            DFS(i+1,depth+1);
            visited[i] = false;
        }
    }
    
    //무조건 자음 2개 모음 1개 이상을 포함해야한다
    public static boolean validCheck(String word){
        int vowel = 0;
        int cos = 0;
        for(int i = 0; i < word.length();i++){
            if (isVowel(word.charAt(i))){
                vowel++;
            }else cos++;
        }

        if (vowel>=1 && cos>=2)return true;
        return false;
    }
 	//모음 판별 
    public static boolean isVowel(char al){
        if (al=='a'||al=='e'||al=='i'||al=='o'||al=='u'){
            return true;
        }else return false;
    }
}

전략

• 일단 단어는 오름차순으로 출력해야되므로 받은 알파벳을 정렬한다.

• DFS를 돌리면서 해당 인덱스의 낱말을 포함하는 경우와 포함하지 않는 케이스로 나눈다

• 재귀 depth가 비밀번호 갯수만큼 사용됐다면 해당 단어를 리스트에 저장한다