문제
어떤 나라에는 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을 출력한다.
풀이
전형적인 그래프 탐색 문제이다. 입력 조건이 N이 최대 30만개로 엄청 크다.. 하지만, 시간제한이 2초기 때문에 O(V+E)인 그래프 탐색(DFS, BFS) 알고리즘을 사용하면 약 O(1,300,000) 이므로 시간 제한에 걸리지 않게 된다.
- 각 노드의 출발 점이 주어지고, 방향이 있는 그래프 문제이다.
- 다익스트라는 아니고, 일반적인 그래프 탐색 문제
- BFS 사용(최단거리 구하는데 쉽다.)
- BFS를 구현할때 기본적으로 방문리스트를 사용하는데, 이 것을 거리+방문 리스트로 변형 시켜 활용하였다.
- 거리는 초기에 모두 -1, 자기 자신은 0으로 초기화
- 방문 시 거리는 -1이 아닐 것이고, 거리는 항상 +1(노드간의 거리는 항상 1)한다.
코드
from collections import deque
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [-1] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b) # 목적지
def bfs(graph, start, distance):
q = deque([start])
distance[start] = 0
while q:
now = q.popleft()
for i in graph[now]:
if distance[i] == -1:
q.append(i)
distance[i] = distance[now] + 1
return distance
result = bfs(graph, x, distance)
solve = False
for i in range(1, n+1):
if distance[i] == k: # 최단 거리를 가진 노드
print(i)
solve = True
if not solve:
print(-1)
