[알고리즘 / 백준] 9997 - 폰트

www.acmicpc.net/problem/9997

9997번: 폰트

 

문제는 위와 같으며, 이 문제의 경우 비트 마스크를 써서 문제를 해결할 수 있습니다. 

 

비트 마스크 알고리즘은 정수의 이진수 표현을 자료구조로 활용하는 방식으로, 숫자를 자리수로 하여 해당 숫자가 포함이 되면 숫자와 같은 자리수를 1로 하고 포함하지 않는 경우는 0으로 하여 빠르게 계산할 수 있는 방식입니다.

 

위 문제에서는 알파벳을 모두 포함하는지 확인해야 하기 때문에 알파벳 26자리를 비트 마스크로 표현하면 다음과 같습니다.

(1 << 26) - 1
# (1 << 26) = 0000 0100 0000 0000 0000 0000 0000 0000
# (1 << 26) - 1 = 0000 0011 1111 1111 1111 1111 1111 1111

 

여기서 << 라는 시프트 연산자를 사용하였는데, 이는 1을 26자리 왼쪽으로 이동시킨다는 의미입니다. 이렇게 하고 - 1 을 하면 26자리가 1로 채워진 수를 얻을 수 있습니다. (모두 1이므로 알파벳 26자리가 모두 포함된 상태를 의미)

 

그리고 각 단어의 비트 마스크를 계산하여 이를 담은 리스트를 만듭니다. 각 단어의 알파벳을 하나씩 돌면서 알파벳의 비트 마스크를 구하고 이를 합치는데 이때 | (or) 연산을 사용합니다. 이 연산은 연산을 하는 두 비트 중 하나만 1이라도 결과가 1이 됩니다. 따라서 이를 이용해 각 단어를 이루는 알파벳을 모두 포함한 비트 마스크를 만들 수 있습니다.

 

단어의 비트 마스크를 담은 리스트를 앞에서부터 해당 단어를 포함하여 문장을 만드는 경우와 포함하지 않고 문장을 만드는 경우를 나눕니다. 최종적으로 만들어진 문장의 비트 마스크가 위에서 생성한 알파벳 26자를 모두 포함하는 비트 마스크와 동일할 시 결과 값을 + 1 하는 방식으로 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다. 파이썬의 경우 결과 제출 시 PyPy3 로 제출해야 시간 초과 없이 문제를 통과할 수 있습니다.

# 재귀, 비트 마스크, 브루투포스 알고리즘, 깊이 우선 탐색
from sys import stdin


def dfs(count, mask):
    global result
    if count == n - 1:  # 단어 사전의 끝까지 간 경우
        if mask == alphabet:  # 지금까지 만들어진 문장의 비트 마스크와 알파벳 26자를 모두 포함하는 비트 마스크 비교
            result += 1
    else:
        dfs(count + 1, mask | words[count + 1])  # 단어를 추가하는 경우
        dfs(count + 1, mask)                     # 단어를 추가하지 않은 경우


alphabet = (1 << 26) - 1

result = 0

n = int(stdin.readline())
words = [0 for _ in range(n)]
for i in range(n):
    word = stdin.readline().strip()  # 각 단어를 알파벳 리스트로 받아서
    for w in word:
        words[i] |= 1 << ord(w) - 97  # 각 알파벳의 위치를 1로 만들기

dfs(-1, 0)

print(result)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    static int n;
    static int[] words;
    static final int alphabet = (1 << 26) - 1;
    static int result = 0;

    public static void main(String[] args) throws Exception {
        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[] word = br.readLine().split("");
            for (String w : word) {
                words[i] |= 1 << w.charAt(0) - 'a';
            }
        }

        dfs(-1, 0);

        System.out.println(result);
    }

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