[백준 / BOJ][Python] 2479 - 경로 찾기

[백준 / BOJ][Python] 2479 - 경로 찾기

https://www.acmicpc.net/problem/2479

2479번: 경로 찾기

걸린 시간 

09 : 22

문제 풀이

간단한 최단 거리 탐색 문제. 가능한 모든 문자열 쌍을 비교하여 해밍 거리가 1이면 간선을 추가한다. 모든 간선의 길이가 1로 같기 때문에, 다익스트라 같은 알고리즘은 필요 없고 단순히 BFS 혹은 DFS로 거리를 구할 수 있다.

코드

import sys, itertools
from collections import deque
input = sys.stdin.readline

def bfs(x):
    global e
    q = deque([(x, [x])])
    visit[x] = 1
    while q:
        x, arr = q.popleft()
        if x == e:
            return arr
        for i in graph[x]:
            if not visit[i]:
                visit[i] = 1
                q.append((i, arr + [i]))
    return [-1]

n, m = map(int, input().split())
code = []
for i in range(n):
    code.append((input().strip(), i + 1))
graph = [[] for _ in range(n + 1)]
for a, b in itertools.combinations(code, 2):
    s1, n1 = a
    s2, n2 = b
    dif = 0
    for i in range(m):
        if s1[i] != s2[i]:
            dif += 1
    if dif == 1:
        graph[n1].append(n2)
        graph[n2].append(n1)
visit = [0 for _ in range(n + 1)]
s, e = map(int, input().split())
print(*bfs(s))