[BOJ]백준 20304번: 비밀번호 제작(Python)/Bitmask, BFS

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

20304번: 비밀번호 제작

익숙한 문제? ㅎㅎ

틀린문제 리스트에 있는게 싫어서 오랜만에 다시 풀어봤다

아주 훌륭한 문제였다 ( = 어렵다는 뜻 )

 

안전거리와 안전도가 등장하는데 안전거리를 구하는 것 자체는 XOR 풀이가 직관적으로 떠오를 수 있지만

비밀번호 후보를 찾는 데에 Bitmask + BFS를 바로 떠올리기는 쉽지 않다

 

항상 특별한 분류의 알고리즘 문제를 풀 때에는 (바로 생각나는 브루트포스 풀이 + 최적화할 수 있는 솔루션 풀이)를 각각 생각하는 편인데

솔루션 풀이는 구글의 도움을 받아 깨우칠 수 있었다 ^^

 

풀 수 있는 핵심 원리는

(시도한 비밀번호) XOR (1이 k개 들어간 임의의 bit) = 비밀번호 후보

이렇게 얻어낸 비밀번호 후보를 다시

(비밀번호 후보) XOR (시도한 비밀번호) = (1이 k개 들어간 임의의 bit)

가 나오고, 이 임의의 bit의 1의 개수가 곧 안전거리 였다.

 

따라서 맨 처음 시도한 비밀번호 후보들은 안전거리 = 0으로 초기화 & 큐에 삽입하고

BFS를 하면서 현재 cur에서 안전거리가 1만큼 차이나는 비밀번호 후보들의 안전거리 갱신 + 큐 삽입

과정을 반복해주면 된다 ❗❗

 

현재 cur에서 안전거리가 1만큼 차이나는 비밀번호 후보들은 (1<<k) shift 한 값을 통해 구할 수 있다

최대 N의 범위가 log2를 씌웠을 때 20자리 이므로 20번의 반복문(0~19)을 돌려 다음 값을 찾을 수 있다

import sys
from collections import deque

input=sys.stdin.readline

n=int(input())
m=int(input())
p=list(map(int,input().split()))
safety=[21 for _ in range(n+1)]
dq=deque()

for i in p: 
    safety[i]=0
    dq.append(i)
    
ans=0

while len(dq)!=0:
    cur=dq.popleft()
    
    for i in range(20):
        x = (1<<i) ^ cur
        if x<=n and safety[cur]+1<safety[x]:
            safety[x]=safety[cur]+1
            ans=max(safety[x],ans)
            dq.append(x)
print(ans)

+ 한 가지 발생했던 이슈는

BFS에 사용했던 queue를 라이브러리가 아닌 list를 이용해서 append(), pop(0)을 이용했는데 시간초과가 발생했다

아마 pop의 시간복잡도가 list 크기 N 기준 O(N)인 듯 하다

 

python에서 큐를 활용할 때 에는 deque를 사용하자 ~~