[파이썬] 백준 20304 : 비밀번호 제작 (플레5)

[파이썬] 백준 20304 : 비밀번호 제작 (플레5)

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

---

풀이

방향성 생각

• 사용한 비밀번호는 안전거리가 0이다.

• 다익처럼 풀면 시간초과할듯?

  • 최대 10만개에서 힙에다가 계속 넣어버림.
  • BFS는 어짜피 100만 2^10~2^11이라 각 자리수에서 최대 11?번이면 도달

• 비트연산으로 해밍거리 1인거부터 차례로 이동하면 OK

---

전체코드

from collections import deque

N = int(input())
M = int(input())
arr = list(map(int,input().split()))

V = [-1]*(N+1)
for a in arr:
    V[a] = 0
leng = len(bin(N))-2

Q = deque(list(zip(arr,[0]*N)))
while Q:
    x,t = Q.popleft()
    for l in range(leng):
        nx = x^(1<<l)
        if 0<=nx<=N and V[nx] == -1:
            V[nx] = t+1
            Q.append((nx,t+1))
print(max(V))

코멘트

• 이왜플?