18352번 특정 거리의 도시 찾기(python3)

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

18352번: 특정 거리의 도시 찾기

최단거리를 찾는 문제이기 때문에 bfs를 적용하여 문제를 해결했다.

from collections import deque

N, M, K, X = map(int, input().split())
Map = [[] for _ in range(N+1)]
for i in range(M):
    x, y = map(int, input().split())
    Map[x].append(y)
distance = [-1] * (N + 1)


#print(Map)
def bfs(Map, X):
    queue = deque()
    distance[X] = 0
    queue.append(X)
    while queue:
        now = queue.popleft()
        for i in Map[now]:
            if distance[i] == -1:
                queue.append(i)
                distance[i] = distance[now] + 1

bfs(Map, X)
#print(distance)
check = False
for i in range(len(distance)):
    if distance[i] == K:
        print(i)
        check = True

if not check:
    print(-1)

문제 풀이중에 거리를 어떻게 적용해야할지 모르겠어서 찾아보았다.

따로 방문했다는 표시만 하는 것이 아니라 distance배열을 도입해서 도시에 처음 방문을 하면 전 도시의 거리에서 +1를해서 거리를 계산했다.