문제
길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.
우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다.
예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다.
- A=000
- B=111
- C=010
- D=110
- E=001
두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다.
우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A와 C의 해밍 거리가 1이고, 코드 C와 D의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A와 E의 해밍 거리는 1이지만, 코드 E와 B의 해밍 거리가 2이므로 해밍 경로가 아니다.
이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.
# 2479
import sys
input = lambda: sys.stdin.readline().strip()
from collections import deque
# 1. 해밍 경로가 1인 두 코드를 그래프에 연결하기
# 2. 코드 A를 시작점으로 하는 최단거리 구하기
n, k = map(int, input().split())
arr = [0] + [int(input()) for _ in range(n)]
graph = []
for _ in range(n+1):
graph.append([])
for i in range(1, n+1):
for j in range(i+1, n+1):
dist = abs(arr[i] - arr[j])
num = 1
for x in range(k):
if dist == num:
graph[i].append(j)
graph[j].append(i)
break
else:
num *= 10
find_min_dist = [-1] * (n+1)
code_dist = [-1] * (n+1)
def bfs():
global n, arr, graph, find_min_dist, code_dist, start, end
queue = deque()
queue.append(start)
code_dist[start] = 0
find_min_dist[start] = 0
while queue:
x = queue.popleft()
if x == end:
continue
for g in graph[x]:
if find_min_dist[g] == -1 or find_min_dist[x] + 1 < find_min_dist[g]:
find_min_dist[g] = find_min_dist[x] + 1
code_dist[g] = x
queue.append(g)
start, end = map(int, input().split())
bfs()
time = find_min_dist[end]
if time == -1:
print(time)
else:
output = [end]
while output[-1] != start:
output.append(code_dist[output[-1]])
output.reverse()
print(*output)