[백준] 1062번 : 가르침

1062번: 가르침

---

[DFS + 백트래킹 + 비트마스킹]

DFS를 이용해 백트래킹을 구현했고, 알파벳 'a' ~ 'z'까지 어떤 알파벳을 알고 있는지에 대한 정보를 비트마스킹으로 표현했다.

즉, 'a', 'b'를 알고있다면 0b00 0000 0000 0000 0000 0000 0011로 나타낼 수 있다.

 

그런데 남극의 단어는 "anta"로 시작해서 "tica"로 끝난다고 했으니, 'a', 'c', 'n', 't', 'i'는 반드시 알고있어야 한다. 그래서 check를 다음과 같이 초기화했다.

int check = (1 << 'a' - 'a') | (1 << 'n' - 'a') | (1 << 't' - 'a') | (1 << 'i' - 'a') | (1 << 'c' - 'a');

이제 K에 대하여 생각해볼 때인데, 남극의 단어는 anta로 시작해서 tica로 끝난다고 했고, 위의 5개 알파벳은 기본적으로 알고있어야 주어지는 단어를 읽을 수 있을지 없을지 여부를 판단할 수 있다. 그러므로 K가 5 미만이면 읽을 수 있는 단어는 0개일 수 밖에 없다. 그리고 K가 5일 때와 K가 6이상일 때의 경우를 나누어 로직을 수행하도록 했다.

 

DFS의 내부는 depth가 K와 같다면 주어진 문자열들과 알고있는 알파벳을 비교하여 모르는게 없다면 읽을 수 있는 단어의 개수를 증가시켜, 그 값이 최대가 되는 값을 따로 저장했다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int max = 0, n, k, check = (1 << 'a' - 'a') | (1 << 'n' - 'a') | (1 << 't' - 'a') | (1 << 'i' - 'a') | (1 << 'c' - 'a');
    static String[] strs;

    static void DFS(int x, int depth){

        if(depth == k){
            int cnt = 0;
            
            for(String str:strs){
                char[] arr = str.toCharArray();
                boolean flag = true;

                for(char c:arr)
                    if((check & (1 << c-'a')) == 0){
                        flag = false;
                        break;
                    }

                if(flag) cnt++;
            }
            max = Math.max(max, cnt);
            return;
        }

        for(int i=x; i<26; i++)
            if((check & (1 << i)) == 0) {
                check |= (1 << i);
                DFS(i, depth + 1);
                check &= ~(1 << i);
            }
    }

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

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

        strs = new String[n];
        for(int i=0; i<n; i++)
            strs[i] = br.readLine();

        if(k == 5)
            DFS(0, 5);

        else if(k > 5) {
            for (int i = 0; i < 26; i++)
                if ((check & (1 << i)) == 0) {
                    check |= (1 << i);
                    DFS(i, 6);
                    check &= ~(1 << i);
                }
        }

        System.out.println(max);
    }
}