[백준 1238] 다익스트라(Dijkstra) - 파이썬 (Python)

파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

---

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다.

다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다.

 

1 -> (2,8) (3,3)

2 -> (4,4) (5,15)

3 -> (4,13)

4 -> (5,2)

5

위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다.

정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.)

1	2	3	4	5
0	INF	INF	INF	INF

그 중 거리가 가장 짧은 1을 채택해서 탐색합니다.

---

1	2	3	4	5
0	8	3	INF	INF

1은 이제 탐색했으므로 방문여부 체크하고 다시 탐색하지 않습니다. 1을 제외한 노드들 중 거리가 짧은 3을 우선적으로 탐색합니다.

---

1	2	3	4	5
0	8	3	3+13	INF

3을 거쳐서 4를 가는 것이므로 13을 더해줍니다.

남아 있는 노드들 중 2가 거리가 작으므로 2를 탐색합니다.

---

1	2	3	4	5
0	8	3	16 / 8+4 = 12	23

2를 탐색했을때 (4,4)이므로 1->2->4 를 거치게 되면 8+4= 12가 됩니다.

그러나 기존에 16이란 값이 있는데, 더 작은 값을 채택해서 12로 결정합니다.

방문하지 않은 노드들 중에서 거리가 12가 가장 낮으므로 4를 탐색합니다.

---

1	2	3	4	5
0	8	3	12	23 / 12 + 5

(5,5) 이므로 12 + 5 해서 17이 되므로 더 작은 17이 체택됩니다.

 이런식으로 5까지 탐색해서 모든 노드의 방문을 마치면 최단거리 탐색이 끝납니다.

---

파이썬 코드

거리가 가장 작은 노드를 골라서 탐색해야되는데, 거리가 작은 노드를 고르는게 시간 복잡도가 큽니다.

그러므로 우선순위 큐를 사용합니다.

(거리, 노드번호) 이렇게 튜플로 넣으면 첫째항인 거리를 우선순위로 내림차순으로 정렬합니다.

계속 탐색하다가 목적지가 나오면 탐색을 멈추고 바로 거리를 저장합니다

# dijkstra
import sys
from queue import PriorityQueue
input = sys.stdin.readline

n,m,x = map(int,input().split())
adjacent = [[]for _ in range(n+1)]
for i in range(m):
    a,b,w = map(int,input().split())
    adjacent[a].append((b,w))

def dijkstra(index , goal):
    dist = [sys.maxsize] * (n+1)
    visited =[False] *(n+1)
    dist[index] = 0
    queue = PriorityQueue()
    queue.put((0,index))
    while queue.qsize()!=0:
        node = queue.get()
        if visited[node[1]]:
            continue
        if node[1] == goal:
            return dist[goal]
        visited[node[1]] = True
        for i in adjacent[node[1]]:
            distance = node[0] + i[1]
            if distance < dist[i[0]]:
                dist[i[0]] = distance
                queue.put((distance , i[0]))

Max = 0
for i in range(1,n+1):
    if i == x:
        continue
    time = dijkstra(i,x) + dijkstra(x, i)
    if time>Max:
        Max = time
    
print(Max)