[백준 1759번] 암호 만들기 - JAVA

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

1759번: 암호 만들기

풀이

사용한 알고리즘 : DFS를 이용한 조합, 백트래킹

 

풀이전략

조합을 사용하여 가질 수 있는 경우의 수를 모두 구한다.

 

단, DFS를 사용해 조합을 만들어 가는 과정에서

현재 탐색 노드의 계층이 마지막 최하위 계층과 동일한 경우에서

모음과 자음의 개수가 주어진 조건대로 모음은 한 개 이상이고, 자음은 두 개 이상이어야 한다.

 

이는 모음의 개수가 한 개 이상이면서 (원하는 결과가 가지는 원소의 개수 -2)개 이하인 경우

자음과 모음의 조건을 충족한다.

 

따라서 조합으로 구하는 경우의 수 중, 모음과 자음의 개수가 조건에 충족되는 경우 출력하면

정답이 도출된다.

 

제출코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int L,C;
    static char arr[];
    static char result[];

    static void dfs(int depth,int beginIndex) throws IOException {
        if(depth==L){
            int vowelCount=0;
            for(int i=0;i<L;++i){
                if(result[i]=='a' || result[i]=='e' || result[i]=='i' ||
                   result[i]=='o' || result[i]=='u'){
                    ++vowelCount;
                }
            }
            if(vowelCount<=L-2 && vowelCount>0){
                bw.write(new String(result)+"\n");
            }
        }
        else{
            for(int i=beginIndex;i<C;++i){
                result[depth]=arr[i];
                dfs(depth+1,i+1);
            }
        }
    }
    public static void main(String args[]) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        dfs(0,0);

        bw.flush();
        bw.close();
    }
}