문제 링크

문제 해설

Idea

  • BFS
  • 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록
  • 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력
  • 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축

Time Complexity

  • BFS: O(N+M) = 1,300,000

Data Size

  • N: 2 <= int <= 300,000
  • M: 1 <= int <= 1,000,000
  • K: 1 <= int <= 300,000
  • X: 1 <= int <= N
  • A, B: 1 <= int <= N

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

N, M, K, X = map(int, input().split())
nodes = [[] for _ in range(N+1)]
visited = [False] * (N+1)
dists = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    nodes[A].append(B)

queue = deque()
queue.append(X)
visited[X] = True

while queue:
    city = queue.popleft()

    for next in nodes[city]:
        if not visited[next] and dists[city] < K:
            queue.append(next)
            visited[next] = True
            dists[next] = dists[city]+1

targets = [i for i,d in enumerate(dists) if d==K]
if targets:
    for target in targets:
        print(target)
else:
    print(-1)