문제

N개의 단어가 포함되어 있는 사전에서, 몇 가지 단어를 이용해 테스트 문장을 만들어야한다. 이때 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야한다. 그리고 각 단어는 한 번씩만 사용해야한다. (순서 무관) 이때 만들 수 있는 테스트 문장의 개수를 구하면 된다.

풀이

어떤 알파벳을 사용했는지 체크할 때 비트 마스크를 사용해서 체크했다.

사용한 자료구조

• ALPHA : 모든 알파벳을 사용했을 경우의 비트마스크이다.
• words[n] : 각 단어의 비트마스크가 들어있는 배열

사용한 함수

DFS를 사용해서 모든 경우의 수를 탐색했다.
매개 변수로 count와 mask를 받는데, 각각 탐색한 depth와 현재까지 사용한 알파벳의 비트마스크 값을 뜻한다.

1. count의 값을 하나씩 증가하면서 분기를 만들어준다.
   (해당 단어를 사용하는 경우, 안 사용하는 경우)
2. count가 n-1 일때 비트마스크의 값이 ALPHA와 같다면 정답에 +1씩 해준다!

소스 코드

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

public class BOJ_9997 {
    static int[] words;
    static int n;
    static int answer;
    static final int ALPHA = (1 << 26) - 1;
    //0000 0100 0000 0000 0000 0000 0000 0000
    //0000 0011 1111 1111 1111 1111 1111 1111

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

        n = Integer.parseInt(br.readLine());
        words = new int[n];

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split("");

            for (int j = 0; j < input.length; j++) {
                //abc ==> 0111
                words[i] |= 1 << input[j].charAt(0) - 'a';
            }
        }

        dfs(-1, 0);

        System.out.println(answer);
    }

    static void dfs(int count, int mask) {
        if (count == n - 1) {
            if (mask == ALPHA) {
                answer++;
            }
        } else {
            dfs(count + 1, mask | words[count+1]);
            dfs(count + 1, mask);
        }
    }
}

풀이 후기

이 문제 풀면서 비트 마스크를 어떻게 사용하는지 확실히 깨달을 수 있었다.
n번째 요소가 있을 때 2진수의 값이 n이 되는 게 아니라, 1을 n만큼 왼쪽으로 쉬프트 연산을 해준다.