알고리즘/백트래킹

[백준 1759] - [백트래킹] - 암호 만들기 (JAVA)

팡스 2018. 12. 26. 15:19

문제 링크 : https://www.acmicpc.net/problem/1759


이 문제는 백트래킹으로 쉽게 접근 할 수 있다. 


이전에 풀었던 백트래킹 문제들을 하나씩 풀어본다면 아주 쉽게 코드를 작성 할 수 있다. 


모든 경우에 수를 전부 탐색하면서 문제에서 제시한 3가지 조건을 만족 시키는 경우 생성된 암호를 출력 해주고 다시 다른 경우의 수를 탐색하면 된다.


이전에 풀었던 백트래킹 문제를 기억해가면서 풀어보니 정말 쉽게 문제를 풀 수 있었다.


만약 기억이 안난다면 다른 백트래킹 문제를 풀어보면서 접근해보면 좋을듯 하다.



백트래킹 관련 글



 



이 문제에서 제시하는 3가지 조건은 아래와 같다.

    • 최소 한개의 모음을 사용해야 한다.

    • 최소 두개의 자음을 사용해야 한다.

    • 알파벳이 증가하는 순서로 나열되어야 한다.

세번째 조건인 알파벳이 증가하는 순서는 굳이 백트래킹 탐색 중 확인할 필요를 느끼지 못해서 알파벳을 전부 입력 받으면 입력받은 알파벳 배열을 정렬한 상태에서 백트래킹을 시도했다.

알파벳은 입력받는 즉시 유니코드로 변경하여 정수형 배열에 저장했다.

char 배열에 저장해도 되지만 혹시나 실수 할 수 있는 부분이 있을까봐 유니코드로 변경하여 정수형 배열에 저장했다.

소스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int L;
    public static int C;
    
    public static int[] arr;
    public static boolean[] visited;
    
    public static final char[] MO_ARR = {'a', 'e', 'i', 'o', 'u'};
    public static StringBuilder sb;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st = new StringTokenizer(br.readLine());
        
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        
        arr = new int[C];
        visited = new boolean[C];
        sb = new StringBuilder();
        
        for(int i=0; i < C; i++) {
            arr[i] = (int)st.nextToken().charAt(0);
        }
        Arrays.sort(arr); // 알파벳이 증가하는 형식이니 배열을 정렬한다.
        
        for(int i=0; i < C; i++) {
            if(i + L > C) continue;
            visited[i] = true;
            backtracking(i, 1, (char)arr[i] + "");
            visited[i] = false;
        }
        
        System.out.println(sb.toString());
    }
    
    public static void backtracking(int idx, int cnt, String str) {
        if(idx >= arr.length || idx + L - cnt > C) return;
        
        if(cnt == L) {
            if(isAble())
                sb.append(str + "\n");
            return;
        }
        
        for(int i = idx+1; i < C; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            backtracking(i, cnt+1, str + (char)arr[i]);
            visited[i] = false;
        }
        
        
    }
    
    public static boolean isAble() {
        int MO_CNT = 0;
        int JA_CNT = 0;
        
        for(int i=0; i < arr.length; i++) {
            if(visited[i]) {
                if(isJa((char)arr[i])) {
                    JA_CNT += 1;
                }else {
                    MO_CNT += 1;
                }
            }
        }
        // 모음이 최소 한개 자음이 최소 두개 있어야 한다.
        if(MO_CNT == 0 || JA_CNT < 2) return false;
        
        return true;
    }
    
    public static boolean isJa(char c) {
        for(int i=0; i < MO_ARR.length; i++) {
            if(c == MO_ARR[i]) return false;
        }
        
        return true;
    }
}
cs


저작자표시