[BOJ] 백준 1759 - 암호 만들기 (자바)

DFS 백트래킹

시작과 동시에 배열을 정렬해줘야햔다. 이거 안봐서 왜틀렸는지 몰랐네;;

그리고 자음 모음 갯수 함수를 반대로해줘야 하는데 똑같이 해서 왜 틀렸는지 몰랏네;;

풀이

1. 백트래킹 형식으로 풀면된다.

2. 자음과 모음 갯수를 파악하면 된다.

3. result[] 배열을 사용해서 선택된 문자가 무엇인지 저장한다.

백트래킹은 하나씩 찍어보면서 푸는게 가장 좋은 것 같다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    static char[] arr;
    static int[] result;
    static int N;
    static int M;
 
    public static void main(String[] args) throws Exception {
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new char[M];
        result = new int[M];
        str = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            arr[i] = str[i].charAt(0);
        }
 
        Arrays.sort(arr); // 문제를 보면 정렬되어 있어야한다....
        DFS(0, 0, 0, 0);
    }
 
    // 시작점, 선택된 문자갯수, 자음갯수, 모음갯수
    public static void DFS(int start, int depth, int ja, int mo) {
 
        for (int i = start; i < M; i++) {
            result[i] = 1; // 선택된 문자 확인용
            // 자음과 모음 갯수를 파악해서 다음으로 넘겨준다.
            DFS(i + 1, depth + 1, ja + (!check(arr[i]) ? 1 : 0), mo + (!check(arr[i]) ? 0 : 1));
 
            result[i] = 0; // 0이면 선택 안됨
        }
        // 문자갯수가 N개이며 자음과 모음의 갯수가 규칙에 맞을때만 출력한다.
        if (depth == N && ja >= 2 && mo >= 1) {
            print();
        }
    }
 
    public static void print() {
        for (int i = 0; i < M; i++) {
            // result가 0이라면 선택되지 않았기 때문에 넘긴다.
            if (result[i] == 1)
                System.out.print(arr[i]);
        }
        System.out.println();
    }
 
    // 자음 모음 파악 함수
    public static boolean check(char a) {
        if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
            return true;
        else
            return false;
    }
 
}