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

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

---

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

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

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

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

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

백트래킹 관련 글 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen 2018/11/23 - [알고리즘/백트래킹] - [백준-1987]-[DFS-백트래킹]-알파벳 2018/12/19 - [알고리즘/BFS_DFS] - [백준 1697] - [bfs] - 숨바꼭질 2018/12/21 - [알고리즘/백트래킹] - [백준 2580] - [백트래킹] - 스도쿠 2018/12/26 - [알고리즘/백트래킹] - [백준 6603] - [백트래킹] - 로또 (JAVA)

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

• 최소 한개의 모음을 사용해야 한다.
  
  
• 최소 두개의 자음을 사용해야 한다.
  
  
• 알파벳이 증가하는 순서로 나열되어야 한다.

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

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

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

소스

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;
    }
}