[15번] 특정거리의 도시 찾기

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

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

 

특정거리의 도시찾기: 최단거리가 K인 모든 도시 찾기 (BFS)

 

• 탐색방향: graph
• 탐색조건: dist == -1
• 탐색결과: 0 -> 1 -> 2 -> ... (최단거리 저장)
• 출발점: S
• 알고리즘 선택: 최단거리 K 까지 탐색 => BFS

 

import collections
import sys
input = sys.stdin.readline  # 간선갯수 100만개

N, M, K, S = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

# BFS
dist = [-1] * (N + 1)
dist[S] = 0
qu = collections.deque([S])
while qu:
    node = qu.popleft()
    if dist[node] == K:  # 최단거리 K 까지 탐색
        break

    for e in graph[node]:
        if dist[e] == -1:
            dist[e] = dist[node] + 1
            qu.append(e)

check = False
for i in range(1, N + 1):
    if dist[i] == K:
        print(i)
        check = True
if check == False:
    print(-1)

4 4 2 1
1 2
1 3
2 3
2 4