🔗
풀이
로그인에 시도된 비밀번호들로부터 최대한 안전거리가 먼 비밀번호를 찾는 문제다. 특정 위치에서 최대한 먼 거리를 찾는 것은 일종의 그래프 탐색이라 할 수 있다. 그래프 탐색에 비유하자면 특정 출발 위치에서 상하좌우로 한 칸씩 탐색 범위를 넓혀가면서 가장 멀리 갈 수 있는 위치를 찾으면 된다. 이 문제에 적용하자면 시도된 모든 비밀번호들로부터 안전거리를 1씩 증가시켜가면서 모든 가능한 숫자(N 이하 정수)를 탐색하고 그 중 최대가 되는 값을 찾으면 된다.
안전거리라는 것은 비밀번호를 2진수로 바꿨을 때, 두 개의 2진수의 서로 다른 자릿수의 개수를 의미한다. 즉, 안전거리가 1인 숫자들은 특정 2진수에서 한 자릿수만 숫자가 바뀐 경우를 찾으면 된다. 3을 예시로 들어보자. 10진법 3을 2진법으로 나타내면 0011이다. 0011에서 각각 한 자리씩만 숫자를 바꿔보면 다음 4가지가 나타날 수 있다. 11이 아니라 0011인 이유는 비교해야 할 최대 숫자 N=10을 2진법으로 나타내면 1010, 4자리이기 때문이다.
그렇다면 한 자리씩 바꾼 숫자는 어떻게 찾아야 할까? 4자리니까 하나씩 비교해가면서 1이면 0으로 0이면 1로 바꾸는 방법이 있을 것이다. 그러나 비트연산자를 생각해보면 둘 중 하나만이 1일 때 1을 반환하는 XOR 연산자가 그 연산을 수행할 수 있다.
<< 연산자를 사용해 1을 한 칸씩 왼쪽으로 이동하며 한 자릿수씩 비교해나갔다. 원래 1이었던 경우 0으로, 0인 경우는 1로 변경하는 걸 알 수 있다. 즉 한 자릿수씩 다르게 할 수 있는것이다. << 연산자와 XOR 연산자를 조합해 안전거리 1의 숫자들을 구할 수 있게 된다.
for i in range(20):
nx = x^(1<<i)N의 최대값인 1,000,000은 이진법으로 20자리이기 때문에 최대 비교할 자리수는 20이 된다. 한자리수씩 비교해나가면서 현재 숫자 x에서 안전거리 1에 위치한 모든 숫자를 찾는 반복문이다.
즉 시도된 비밀번호를 전부 큐에 넣고 시작한다. 처음 큐에 들어있는 처음 시도된 비밀번호들은 안전거리가 0이다. 이 비밀번호들로부터 안전거리 1에 있는 모든 숫자를 찾고 다시 큐에 넣는다. 이제 안전거리 1인 큐에 들어있는 숫자들을 꺼내서 다시 그 숫자들로부터 안전거리 1에 있는 숫자들을 찾으면 그 숫자들은 처음 시도된 비밀번호에서 안전거리 2에 있는 숫자들이 된다.
단 Python3으로는 deque(), sys.stdin,readline 없으면 시간초과 난다. 비교해야 할 자릿수 최대값은 그냥 20으로 구해도 되지만 N이 계속 변하기 때문에 N을 이진법으로 바꿨을 때의 길이만큼만 구하도록 n이란 변수를 추가했는데 그닥 시간이 줄어든 것 같진 않다.
# 비밀번호 제작
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
M = int(input())
visited = [-1]*(N+1)
queue = deque()
lst = list(map(int, input().split()))
for x in lst:
visited[x] = 0
queue.append(x)
max_dist, n = 0, len(bin(N))-2
while queue:
x = queue.popleft()
for i in range(n):
nx = x^(1<<i)
if nx>N or visited[nx] != -1:
continue
visited[nx] = visited[x]+1
queue.append(nx)
max_dist = max(max_dist, visited[nx])
print(max_dist)후기
사실 이 문제는 혼자 풀진 못했고, 이 풀이를 참고했다.
