[백준 2481번] 해밍 경로 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

def printpath(x):
  if x == 1:
    print(1,end=" ")
    return
  printpath(path[x])
  print(x,end=" ")

N,K = map(int,input().split())

num = {}
code = {}
for i in range(1,N+1):
  c = input().strip()
  num[c] = i
  code[i] = c

path = {i:-1 for i in range(1,N+1)}
path[1] = 1

dq = deque([1])
while dq:
  now = dq.popleft()
  clist = [*code[now]]
  for i in range(K):
    clist[i] = str(abs(int(clist[i])-1))
    c = "".join(clist)
    clist[i] = str(abs(int(clist[i])-1))
    if num.get(c):
      next = num[c]
      if path[next] == -1:
        dq.append(next)
        path[next] = now

M = int(input())    
for i in range(M):
  j = int(input())
  if path[j] == -1:
    print(-1)
  else:
    printpath(j)
    print()

BFS로 해결하였다.

 

이 문제에서 가장 큰 관건은 해밍경로가 1인 경로를 어떻게 찾아주냐였는데, 비트연산을 이용하고 싶어서 고민해봤지만 비트에 대한 개념 부족으로 포기하였다. 

그래서 내가 선택한 방법은 그냥 코드를 문자열로 저장하고, BFS를 찾을때는 문자열을 list로 변환한 후, 인덱스 하나만 변경시킨 뒤 join함수로 다시 문자열로 만드는 방법이었다.

 

알고리즘을 요약하면

1. 코드와 번호에 대해서 num[코드] = 번호, code[num] = 번호 가 뜨게끔 dictionary를 만들어준다.

2. 번호에 대한 path dictionary도 만들어준다. 이때 초기값은 -1로 설정한다.

3. BFS를 실행, 위에서 말한 방법으로 해밍경로가 1인 문자열을 dict.get 함수를 이용해서 찾아주고, 존재하면 해당 번호의 path를 현재 번호로 저장한다.

4. path를 재귀함수로 역추적하여 출력한다.

 

이때 path를 재귀함수로 출력하는 방법은 좋은 방법이 아니었던 것 같다.

그냥 편하려고 저렇게 했는데, recursion error가 나버려서, while문으로 하는게 낫지 않았을까 싶다.

 

 

오늘의 교훈) 비트연산에 대해 공부하고, 경로 역추적은 왠만하면 재귀함수로 하지말자