[JAVA] 백준 (골드4) 1062번 가르침

링크

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

---

입력 예제

3 6
antarctica
antahellotica
antacartica

---

출력 예제

2

---

풀이

단어의 최대 길이는 15이므로 필수적으로 배워야 하는 알파벳을 제외하면 10개를 더 배워야 한다. 21개의 알파벳 중에 10개를 뽑는 경우의 수는 약 35만 ($\binom{21}{10} = 352716$), 단어의 개수는 최대 50개 이므로 $50 × 350,000 = 17,500,000$이다. 완전 탐색이 가능하며 가능한 경우에 대해 가지치기를 한다.

배운 알파벳을 체크하기 위해 boolean 배열을 사용할 수도 있지만 알파벳이기 때문에 비트마스크를 이용하면 더욱 최적화를 할 수 있다. 가령 c를 체크하기 위해서는 다음과 같이 할 수 있다.

int learned = 0;          // 초기값 (00000000 00000000 00000000 00000000)
learned |= (1 << ('c' - 'a')); // 'c'의 위치를 1로 변경

가지치기를 하기 위해 특정 문자를 원복하기 위해서는 다음과 같이 할 수 있다.

learned = 00000000 00000000 00000000 00101101  (기존 값)
1 << 2  = 00000000 00000000 00000000 00000100  (i = 2)
~(1 << 2) = 11111111 11111111 11111111 11111011
--------------------------------------
learned &= ~(1 << 2)
        = 00000000 00000000 00000000 00101001  (i번째 비트가 꺼짐)

따라서 백트래킹은 다음과 같이 진행할 수 있다.

learned |= (1 << i);  //i번째 알파벳 학습 (비트 1로 설정)
backtracking(i + 1, count + 1);
learned &= ~(1 << i);  //i번째 알파벳 잊음 (비트 0으로 설정) → 백트래킹

입력된 단어 또한 비트마스크로 저장하여, 모든 알파벳에 대해 탐색을 진행하며 백트래킹을 하고 K개의 알파벳을 배웠을 때 배울 수 있는 단어의 수를 카운트한다.

private static void recur(int index, int count) {
    if (count == K) {
    
        //배운 문자로 읽을 수 있는 단어 카운트
        int temp = 0;
        for (int word : words) {
            if ((word & learned) == word) {
                temp++;
            }
        }
        
        max = Math.max(max, temp);
        return;
    }
    
    for (int i = index; i < ALPHABET_SIZE; i++) {
        int cur = 1 << i;  //현재 문자의 비트마스크
        if ((learned & cur) == 0) {  //배우지 않은 문자라면
            learned |= cur;  //i번째 문자 추가
            recur(i + 1, count + 1);
            learned &= ~cur;  //i번째 문자만 제거 (백트래킹)
        }
    }
}

전체 코드

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

/*
백준 / 가르침 / 골드4
https://www.acmicpc.net/problem/1062
 */
public class Main {

    private static final int ALPHABET_SIZE = 26;
    private static int N, K;
    private static int learned = 0;
    private static int max = 0;
    private static int[] words;

    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());  //1~50
        K = Integer.parseInt(st.nextToken());  //0~26

        if (K < 5) {
            System.out.println(0);
            return;
        }

        //acint는 필수로 배워야 함
        for (char c : "acint".toCharArray()) {
            learned |= (1 << (c - 'a'));  //비트마스크로 체크
        }

        words = new int[N];
        for (int i = 0; i < N; i++) {
            for (char c : br.readLine().toCharArray()) {
                words[i] |= (1 << (c - 'a'));  //단어를 비트마스크로 저장
            }
        }

        recur(0, 5);

        System.out.println(max);
    }

    private static void recur(int index, int count) {
        if (count == K) {

            //배운 문자로 읽을 수 있는 단어 카운트
            int temp = 0;
            for (int word : words) {
                if ((word & learned) == word) {
                    temp++;
                }
            }

            max = Math.max(max, temp);
            return;
        }

        for (int i = index; i < ALPHABET_SIZE; i++) {
            int cur = 1 << i;  //현재 문자의 비트마스크
            if ((learned & cur) == 0) {  //배우지 않은 문자라면
                learned |= cur;  //i번째 문자 추가
                recur(i + 1, count + 1);
                learned &= ~cur;  //i번째 문자만 제거 (백트래킹)
            }
        }
    }
}