[백준] 18352번 - 특정 거리의 도시 찾기

문제 분석

모든 도로의 거리가 1이므로 가중치가 없는 인접 리스트로 이 그래프를 표현할 수 있다.
도시의 개수가 300,000, 도로의 최대 크기가 1,000,000이므로 BFS 탐색을 수행하면 해당 문제를 해결할 수 있다.

소스 코드

# 특정 거리의 도시 찾기
from collections import deque
import sys
input = sys.stdin.readline

N, M, K, X = map(int, input().split())
arr = [[] for _ in range(N + 1)]
visited = [False for _ in range(N + 1)]
Result = []
que = deque()

for _ in range(M):
    start, end = map(int, input().split())
    arr[start].append(end)

que.append((X, 0))

while len(que) > 0:
    node, distance = que.popleft()
    visited[node] = True

    if distance == K:
        Result.append(node)
        continue
    else:
        for i in arr[node]:
            if not visited[i]:
                visited[i] = True
                que.append((i, distance + 1))

if Result:
    Result.sort()
    for v in Result:
        print(v)
else:
    print(-1)