[백준] 9997번: 폰트 - 비트마스킹 Python

 

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

9997번: 폰트

 

* 비트마스킹을 사용할 수 있는 이유 : 알파벳 26자리 방문 표시를 0 or 1 로 할 수 있음 

ex) 1 << 26 을 하면 1을 26자리 왼쪽으로 이동시킬 수 있다

이러면 0의 개수가 26개이며, 0 이 아직 방문되지 않은 알파벳이라는 의미 , 1 은 방문한 알파벳이라는 의미로 사용할 수 있다. 

1 << 26 : 0100 0000 0000 0000 0000 0000 0000

 

1 << 26 - 1 연산을 해주면 1 뒤의 0 들이 1로 바뀌게 된다. 

1 << 26 - 1 : 0011 1111 1111 1111 1111 1111 1111

 

* 각 단어의 알파벳의 정보를 bit로 표현할 수 있다. 

    for c in word:
        # OR 연산하면 알파벳 있는 경우 1로 저장
        word_list[i] |= 1 << ord(c) - 97 # ord('a') 가 97 임

 

| 은 OR 연산으로 1 또는 0 을 만나면 1이 된다. 이는 알파벳을 방문 유무를 처리할 때 사용한다. 

 

apple 에서 이미 a 가 나왔다면 1 + 1 이므로 그대로 1 이고 

p 는 처음 등장하는 것이라면 1 + 0 이므로 1로 표시할 수 있기 때문이다. 

N = int(input()) # 단어 개수
answer = 0
# # 알파벳 26개 모두 포함하는 단어 조합의 개수 찾기

word_list = [0] * N # 각 단어에 대해 알파벳 정보를 0 1 로 저장한다.

for i in range(N):
    word = input()
    for c in word:
        # OR 연산하면 알파벳 있는 경우 1로 저장
        word_list[i] |= 1 << ord(c) - 97 # ord('a') 가 97 임

# check = [0] * 26 # 알파벳 방문 여부 표시
# 1 << 26 : 1을 26자 왼쪽으로 이동시키기 0100 0000 0000 0000 0000 0000 0000
check = (1 << 26) - 1 # 0011 1111 1111 1111 1111 1111 1111 (알파벳 26자리 방문 여부를 저장하기 위해서 비트 사용 )

def solve(index, visited):
    global N, answer
    if index == N-1:
        if visited == check:
            answer += 1
        return
    solve(index+1, visited | word_list[index+1]) # 현재 단어 추가 -> | 는 OR 연산
    solve(index+1, visited)

solve(-1, 0)

print(answer)