[백준]1062번. 가르침(JAVA)

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

---

문제

---

풀이

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

public class Main {

    static int n, k;
    static int max = Integer.MIN_VALUE;
    static boolean[] visited;
    static String[] word;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

         st = new StringTokenizer(br.readLine());

         n = Integer.parseInt(st.nextToken());
         k = Integer.parseInt(st.nextToken());

         word = new String[n];

         for(int i = 0; i < n; i++){
             String str = br.readLine();
             word[i] = str.substring(4,str.length() - 4);
         }

         if(k<5){
             System.out.println(0);
             return;
         } else if (k == 26) {
             System.out.println(n);
             return;
         }

        visited = new boolean[26]; //각 알파벳을 배웠는지 체크
        visited['a' - 'a'] = true;
        visited['c' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;

        dfs(0,0);

        System.out.println(max);


    }

    public static void dfs(int index, int len){
        if(len == k-5){
            int count = 0;
            for(int i = 0; i < n; i++){
                boolean check = true;
                for(int j = 0; j < word[i].length(); j++){
                    if(!visited[word[i].charAt(j) - 'a']){
                        check = false;
                        break;
                    }
                }
                if(check) count++;
            }
            max = Math.max(max, count);
            return;
        }

        for(int i = index; i < 26; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                dfs(i+1, len + 1);
                visited[i] = false;
            }
        }
    }


}

 

천천히 살펴보자.

먼저 사용자 입력을 받은 문자열에서 앞의 네글자와 뒤의 네글자를 제외하고 받는다.(필수적으로 들어오는 문자이기 때문이다)

후에 배울 수 있는 문자의 크기가 5보다 작거나 26과 동일하다면 예외적으로 바로 답을 출력한다.(이런 식으로 가능하다면 먼처 처리하고 끝내는 것이 효율이 좋다.)

알파벳 26개에 대해 인덱스를 두고 학습을 진행할 것이다. 대신 꼭 배워야하는 antic에 대해서는 먼저 true처리를 해준다.

이때 꼭 알면 좋은 것이 'a'-'a'가 알파벳의 0번 인덱스이다! 즉 알파벳 - 'a'를 해주면 내가 알고있는 순서가 나오게 된다.

 

이후 dfs부분에서는 백트레킹과 조합을 이용한 방식이다.

len이 k-5가 될때까지 진행한다.

a부터 인덱스를 하나씩 순회하며 모든 조합을 테스트해볼 때까지 진행하며 이 때마다 max값이 갱신될 수 있음을 확인해주면 된다.