특정 거리의 도시 찾기

풀이

 그래프 최단 거리 문제이므로 다익스트라 or BFS로 접근해야겠다고 생각했다. 나는 아래와 같이 BFS로 풀었다. 예외 찾느라 고생했는데 처음에 나는 result를 다 0으로 초기화했었는데 이 때문에 시작점을 다시 방문하게 되버리는 문제가 발생했었다.

from collections import deque
import sys
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
result = [-1 for i in range(N+1)]

for i in range(1, M+1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
result[X] = 0
queue = deque([X])
flag = 0
while(queue):
    r = queue.popleft()
    for s in graph[r]:
        if result[s] == -1:
            result[s] = result[r] + 1
            queue.append(s)


for i in range(1, N+1):
    if result[i] == K:
        flag = 1
        print(i)

if flag == 0:
    print(-1)

시간복잡도 : O(n+m) (N,M에 대해)