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

2024년 5월 28일

문제 링크 : 백준 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을 출력한다.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 최단 경로

---

문제 접근

 

시작 정점에서 모든 정점까지의 최단 거리를 탐색해야 한다는 점에서 다익스트라 알고리즘을 사용해야 한다고 판단했다.

 

모든 정점까지의 거리를 구한 후, 거리가 K인 도시를 출력하면 되며 만약 그런 도시가 존재하지 않는다면 -1을 출력하면 된다.

 

---

순서도

 

1. 노드의 개수 N, 간선의 개수 M, 도달 거리 K, 출발 도시 X를 입력받는다.

2. 그래프를 인접리스트 형태로 입력받는다. 또한 각 도시까지의 거리를 담을 distance 배열을 선언한다.

3. X를 시작점으로 모든 정점에 대한 최단 거리를 알아내기 위해 다익스트라 알고리즘을 이용한다.
3-1. 우선순위 큐를 사용하기 위해 최소 힙 구조의 hq를 선언한다.
3-2. 현재 방문 노드와 현재 노드까지의 거리를 heappop()한다. 
3-3. 현재 방문 노드와 이어진 다음 노드에 거리 1을 더해보고 지금까지 구한 최단 거리보다 짧다면 
	 hq에 해당 노드와 해당 노드까지의 거리를 heappush하고 distance를 갱신해준다.
3-4. 3-1 ~ 3-3 과정을 hq가 빌 때까지 반복한다.

4. distance를 하나씩 탐색해보며 최단 거리가 K인 도시를 출력하고, 없다면 -1을 출력한다.

 

 

---

입력 예제

 

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

 

 

 

출력 예제

 

4

 

---

전체 코드

 

# 18352
import sys
import heapq

input = sys.stdin.readline

def dijkstra(start_v):
    hq = []
    heapq.heappush(hq, [0, start_v])

    while hq:
        now_dis, now_v = heapq.heappop(hq)

        for next_v in city[now_v]:
            if distance[next_v] > now_dis + 1:
                distance[next_v] = now_dis + 1
                heapq.heappush(hq, [distance[next_v], next_v])
    

if __name__ == "__main__":
    N, M, K, X = map(int, input().split())
    
    city = [[] for _ in range(N + 1)]

    for _ in range(M):
        v1, v2 = map(int, input().split())
        city[v1].append(v2)
    
    INF = 10**6 + 1
    distance = [INF] * (N + 1)
    distance[X] = 0

    dijkstra(X)

    is_exist = False

    for i in range(1, N + 1):
        if distance[i] == K:
            print(i, end=" ")
            is_exist = True
    
    if not is_exist:
        print(-1)

---

풀이 후기

 

모든 간선의 가중치가 1인 그래프를 탐색하는 간단한 문제였다.

 

다익스트라 알고리즘을 활용해보기엔 좋은 문제라 생각한다.