[Java] 백준 1062번: 가르침

[문제 바로 가기] - 가르침

유형 : 비트마스킹, 백트래킹

💡 아이디어

항상 이런 문제가 있을 때마다 비트마스킹을 사용하는게 편리하단걸 알면서도 사용하지 않았는데 이번에 사용하는 법을 익혀보려고 한다.

모든 단어는 anta로 시작되고 tica로 끝나므로 a, n, t, i, c는 무조건 배워야 하고 K에서 5를 빼고 시작해야 한다. 만약 5를 뺀 K가 0보다 작다면 학생들이 읽을 수 있는 단어는 없으므로 0을 바로 출력한다.

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            int bit = 0;

            for (char c : s.toCharArray()) {
                // << : 왼쪽 시프트 연산자
                // |= : 비트 OR 연산자
                // 한 단어의 알파벳 집합을 bit에 저장
                bit |= (1 << (c - 'a'));
            }

            words[i] = bit;
        }

단어들을 입력 받으면서 한 글자씩 bit와 OR 연산을 한다.
이때 char c에서 'a'를 빼는 이유는 알파벳의 아스키코드, 즉 인덱스를 매긴다고 생각하면 된다.

1 << c는 알파벳의 인덱스를 왼쪽 시프트 연산자인 <<를 사용해서 기록한다.
만약 c가 알파벳 a라면 00000001, c라면 00000100, z라면 10000000000000000000000000가 되는 것이다.

마지막으로 bit와 OR 연산을 함으로써 하나의 단어에 있는 모든 알파벳을 bit에 기록한다.

이후 a, n, t, i, c가 포함된 비트를 dfs에 넣어 탐색을 시작한다.

        for (int i = idx; i < 26; i++) {
            // 이미 배운 문자면 스킵
            if ((learn & (1 << i)) != 0) continue;

            // 아직 배우지 않은 문자라면 탐색
            dfs(i + 1, count + 1, learn | (1 << i));
        }

알파벳 a부터 z까지 탐색하면서 이미 배운 문자라면 굳이 다시 탐색하지 않고, 아직 배우지 않은 문자라면 learn 비트에 기록하고 탐색을 시작한다.

        if (count == K) {
            int readable = 0;

            for (int word : words) {
                // work에 있는 알파벳이 모두 learn에 포함된다면
                if ((word & learn) == word) {
                    readable++;
                }
            }

            answer = Math.max(answer, readable);
            return;
        }

K번만큼 탐색을 한 뒤, 각 단어의 알파벳이 learn에 모두 포함된다면 학생들이 읽을 수 있는 글자가 되는 것이다.

---

풀이

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

/**
 * a, n, t, i, c는 항상 가르쳐야 하므로 K에서 5 빼기
 */

public class BJ_1062_가르침 {
    static int N, K;
    static int[] words;
    static int answer = 0;

    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());

        words = new int[N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            int bit = 0;

            for (char c : s.toCharArray()) {
                // << : 왼쪽 시프트 연산자
                // |= : 비트 OR 연산자
                // 한 단어의 알파벳 집합을 bit에 저장
                bit |= (1 << (c - 'a'));
            }

            words[i] = bit;
        }

        // a, n, t, i, c는 무조건 배워야 함
        if (K < 5) {
            System.out.println(0);
            return;
        }

        K -= 5;

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

        dfs(0, 0, learn); // a, n, t, i, c가 포함된 비트

        System.out.println(answer);
    }

    static void dfs(int idx, int count, int learn) {
        if (count == K) {
            int readable = 0;

            for (int word : words) {
                // word에 있는 알파벳이 모두 learn에 포함된다면
                if ((word & learn) == word) {
                    readable++;
                }
            }

            answer = Math.max(answer, readable);
            return;
        }

        for (int i = idx; i < 26; i++) {
            // 이미 배운 문자면 스킵
            if ((learn & (1 << i)) != 0) continue;

            // 아직 배우지 않은 문자라면 탐색
            dfs(i + 1, count + 1, learn | (1 << i));
        }
    }
}