[DFS/BFS] Q15 특정 거리의 도시 찾기

난이도: 1.5 / 풀이 시간: 30분
link: https://www.acmicpc.net/problem/18352

어떤 나라에는 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입 니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한 출발 도시 X에서 출발 도시 X로 가 는 최단 거리는 항상 0이라고 가정합니다.

예를 들어 N = 4, K= 2. X= 1일 때 다음과 같이 그래프가 구성되어 있다고 합시다. 이때 1번 도시에서 출발하여 도달할 수 있는 도시 중에 서, 최단 거리가 2인 도시는 4번 도시뿐입니다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않습니다.

입력 조건

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어집니다.
  (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N)
• 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어지며, 각 자연수는 공백으로 구분합니다.
  이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미입니다. (1 ≤ A, B ≤ N)
  단, A와 B는 서로 다른 자연수입니다.

출력 조건

• X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력합니다.
• 이때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력합니다.

입력 예시 1

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

출력 예시 1

4

---

풀이특징

• BFS (deque 사용)
• 간선의 비용이 1로 동일하므로 BFS 사용이 수월
• BFS를 통해 방문하면서 이전 노드의 depth + 1로 설정하며 k값이랑 같은 경우 출력

from collections import deque
# x로부터 출발하여 최단 거리가 정확히 k인 모든 도시의 번호를 출력
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)

distance = [0] * n
q = deque([x-1])

results = []
while q:
    now = q.popleft()
    
    for node in graph[now]:
        if distance[node] == 0:
            q.append(node)
            distance[node] = distance[now]+1
            if distance[node] == k:
                results.append(node)

results.sort()
if len(results) == 0:
    print(-1)
else:
    for i in results:
        print(i+1)