(Python) - BOJ(18352번) : 특정 거리의 도시 찾기

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

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

---

• 문제 : 

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

 

 

---

• 풀이 :

BFS로 해결할 수 있는 문제이다. 모든 간선의 가중치가 1로 동일하기 때문에 너비우선탐색으로 K만큼의 거리를 갖고 있는 도시를 쉽게 찾을 수 있다.

 

그러나 나는 다익스트라를 공부하는 중이여서 다익스트라로 구현하였다. queue대신 heap을 사용하고, cost가 낮은 경로를 우선순위로 탐색했다는 점을 빼면 BFS와 원리가 동일하다.

 

 

 

---

• 소스코드 : 

import sys
from heapq import heappop,heappush
input = sys.stdin.readline


N,M,K,X = map(int,input().split())
graph = [[] for _ in range(N+1)]
distance = [float('inf') for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append([b,1])
heap = []
heappush(heap,[0,X])
distance[X] = 0
while heap:
    cost,curr = heappop(heap)
    for next, c in graph[curr]:
        totalCost = cost+c
        if distance[next] > totalCost:
            distance[next] = totalCost
            heappush(heap,[totalCost,next])
if K not in distance:
    print(-1)
    exit()
for i in range(1,N+1):
    if distance[i] == K:
        print(i)