이번 문제는 너비우선탐색과 비트마스킹을 함께 사용하여 풀이하였다. 혼자의 힘으로는 접근하기에 어려웠기 때문에 구글링의 힘을 빌려서 해결하였다. 이 문제에서의 핵심은 (시도한 비밀번호) 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)