이번 문제는 BFS를 활용하여 해결하였다. 처음에는 해밍턴 거리를 구하기 위해 XOR연산자를 활용하였는데, 이 방법을 쓰는 과정에서 에러가 발생하였다. K의 길이가 최대 30인 것을 보고, 그냥 for문을 통해 확인하는 방식으로 구현하였고, 해결할 수 있었다.

Code

from collections import deque
n, k = map(int, input().split())
nodes = ['']+[str(input()) for _ in range(n)]
start, end = map(int, input().split())
answer = []
def get_path():
    global answer
    q = deque()
    q.append((start, [start]))
    visited = [False for _ in range(n+1)]
    visited[start] = True
    while q:
        idx, path = q.popleft()
        if idx == end:
            return path
        for i in range(1, n+1):
            cnt = 0
            if not visited[i]:
                for j in range(k):
                    if nodes[idx][j] != nodes[i][j]:
                        cnt += 1
                    if cnt > 1:
                        break
                if cnt == 1:
                    visited[i] = True
                    q.append((i, path+[i]))
    return [-1]
print(*get_path())