백준 1759번 : 암호 만들기 java

이 문제는 데이터를 입력받은 후 dfs를 이용하여 중복된 값이 나오지 않게 탐색하는 알고리즘입니다.

이 문제를 풀 때 조심해야하는 점은 모음이 1개 이상, 자음이 2개 이상 들어가야 한다는 조건입니다.

문자들을 입력받은 후 정렬하여 dfs를 실행하며 모음이 1개 이상, 자음이 2개 이상 들어 있는지 확인하면 되는 문제입니다.

바로 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static char[] charArr;
    static int L, C;
    static char[] answer;
    static boolean[] visited;

    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());

        charArr = new char[C];
        answer = new char[L];
        visited = new boolean[C];

        String[] input = br.readLine().split(" ");
        for(int i = 0; i<C; i++)
            charArr[i] = input[i].charAt(0);

        Arrays.sort(charArr);
        dfs(0, 0);
    }
    static void dfs(int idx, int cnt){
        if(cnt == L){
            boolean check = check();
            if(!check)
                return;

            for(int i = 0; i<L; i++)
                System.out.print(answer[i]);
            System.out.println();

            return;
        }

        for(int i = idx; i<C; i++){
            if(!visited[i]){
                visited[i] = true;
                answer[cnt] = charArr[i];
                dfs(i, cnt+1);
                visited[i] = false;
            }
        }
    }

    static boolean check(){
        int aeiou = 0;
        for(int i = 0; i<L; i++){
            switch(answer[i]){
                case 'a':
                case 'e':
                case 'i':
                case 'o':
                case 'u':
                    aeiou++;
            }
        }

        if(aeiou>0 && L-aeiou>1)
            return true;

        return false;
    }
}

이 블로그의 다른 dfs를 이용한 문제들과 유사한 문제였습니다.