[백준 알고리즘] 2479. 경로찾기 _ 파이썬

 

처음에는 그래프로 만들어서 풀어봤는데, 

 

그래프로 만들다 보니 가지 않는 정점까지 찾아서 다 돌리다보니 시간초과가 났다.

 

그래서 그냥 큐로 돌리고 방문표시를 통해 되돌아가는 일이 없게 하니 통과했다!

 

from collections import deque

def hamming():
    visited[s] = 1
    Q = deque()
    Q.append((s, str(s)))
    while Q:
        num, code = Q.popleft()
        if num == e : return code
        for i in range(1, N+1):
            cnt = 0
            if visited[i]: continue
            for j in range(K):
                if arr[num][j] != arr[i][j]:
                    cnt += 1
                if cnt > 1:
                    break
            if cnt == 1:
                visited[i] = 1
                Q.append((i, code + ' ' + str(i)))

    return -1



N, K = map(int, input().split())
arr = ['0']+[input() for _ in range(N)]
s, e = map(int, input().split())
visited = [0] * (N+1)
print(hamming())