우주의 IT 소행성

from collections import deque
import sys
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

# 모든 도시 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0  # 출발 도시에서 출발 도시까지 거리는 0

# 모든 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

# BFS 실행
queue = deque([x])
while queue:
    now = queue.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            queue.append(next_node)

# 최단 거리가 K인 도시의 번호 오름차순 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 최단 거리가 K인 도시가 없을 때 -1 출력
if check == False:
    print(-1)

BFS를 사용하여 푼 문제

그래프에서 모든 간선의 비용이 동일할 때에는 너비 우선 탐색으로 손쉽게 해결할 수 있다.

노드의 개수 N의 최대 : 30000

간선의 개수 M의 최대 : 10000

O(N + M)으로 해결해야 하는 문제로, 특정 도시 X를 시작점으로 BFS를 수행해 모든 도시까지의 최단 거리를 계산한 후, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 출력한다.