[ BOJ / Python ] 20304번 비밀번호 제작
이번 문제는 너비우선탐색과 비트마스킹을 함께 사용하여 풀이하였다. 혼자의 힘으로는 접근하기에 어려웠기 때문에 구글링의 힘을 빌려서 해결하였다. 이 문제에서의 핵심은 (시도한 비밀번호) XOR (1이 k개 들어간 임의의 bit) = 비밀번호 후보
를 통해 얻은 비밀번호 후보
를 사용하여 (비밀번호 후보) XOR (시도한 비밀번호) = 1이 k개 들어간 임의의 bit
를 다시 구하게 되고 이때 임의의 bit의 1의 개수가 안전거리가 된다는 것이다.
그러므로 현재의 안전거리와 안전거리가 1 차이나는 비밀번호 후보들의 안전거리를 갱신하는 방법으로 하여 해결하였다. 너비우선탐색이기 때문에 비밀번호 후보들의 안전거리를 갱신할 때에 큐에 비밀번호 후보를 넣어주어 이 후보에 대한 탐색도 진행될 수 있도록 해야한다.
- n을 입력받는다.
- m을 입력받는다.
- 시도한 비밀번호 리스트 hacker를 입력받는다.
- 최대 길이를 나타내는 변수 mx_len에 n을 이진수로 변환했을 때의 길이를 저장한다.
- 안전거리 리스트 safety를 mx_len+1 n+1개로 채운다.
- 너비우선탐색에 사용할 큐 dq를 deque로 선언한다.
- hacker를 순회하는 i에 대한 for문을 돌린다.
->safety[i]
를 0으로 갱신한다.
-> dq에 i를 넣는다. - 정답을 저장할 변수 answer를 0으로 선언한다.
- dq가 존재하는 동안 반복하는 while문을 돌린다.
-> dq에서 cur을 추출한다.
-> mx_len만큼 반복하는 i에 대한 for문을 돌린다.
--> 임시 변수 x에(1이 i개 들어간 임의의 bit) XOR (현재 비밀번호 후보)
의 값을 저장한다.
--> 만약 x가 n보다 작거나 같고,safety[cur]+1
이safety[x]
보다 작을 경우,
--->safety[x]
를safety[cur]+1
로 갱신한다.
---> answer를safety[x]
와 answer 중 더 큰 값으로 갱신한다.
---> dq에 x를 넣는다. - answer를 출력한다.
Code
import collections
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
hacker=list(map(int, input().split()))
mx_len=len(bin(n)[2:])
safety=[mx_len+1 for _ in range(n+1)]
dq=collections.deque()
for i in hacker:
safety[i]=0
dq.append(i)
answer=0
while dq:
cur=dq.popleft()
for i in range(mx_len):
x=(1<<i)^cur
if x<=n and safety[cur]+1<safety[x]:
safety[x]=safety[cur]+1
answer=max(safety[x], answer)
dq.append(x)
print(answer)
import collections
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
hacker=list(map(int, input().split()))
mx_len=len(bin(n)[2:])
safety=[mx_len+1 for _ in range(n+1)]
dq=collections.deque()
for i in hacker:
safety[i]=0
dq.append(i)
answer=0
while dq:
cur=dq.popleft()
for i in range(mx_len):
x=(1<<i)^cur
if x<=n and safety[cur]+1<safety[x]:
safety[x]=safety[cur]+1
answer=max(safety[x], answer)
dq.append(x)
print(answer)
Author And Source
이 문제에 관하여([ BOJ / Python ] 20304번 비밀번호 제작), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-20304번-비밀번호-제작저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)