[baekjoon] 백준 1238번 : 파티 (by python 파이썬) 다익스트라 최단경로, heapq

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

1238번: 파티

 

정답 code

#파티
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) #무한 설정

n,m,x = map(int,input().split())
road = [[] for _ in range(n+1)]

for _ in range(m):
    s,e,time = map(int,input().split())
    road[s].append((e,time))

def dijkstra(start):
    q = []
    #다른 노드로가는 최단거리 무한으로 설정
    distance = [INF] *(n+1)
    
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, node = heapq.heappop(q)
        
        if distance[node] >= dist:
            for node_index, node_time in road[node]:
                time = dist + node_time
                #원래 소요시간보다 새로운 소요시간이 더 작다면
                if distance[node_index] > time:
                    #소요시간 교체
                    distance[node_index] = time
                    heapq.heappush(q,(time,node_index))

    return distance

result = 0
for i in range(1,n+1):
    go = dijkstra(i) 
    back  =dijkstra(x)
    result = max(result,go[x] + back[i])

print(result)

 

solution

이문제를 처음 풀때에는 bfs나 dfs를 이용 하여 해결하려 하였다.

하지만 위의 경우는 간선의 최소를 구하는 것이 아닌 각 간선의 시간의 소요시간이 따로있고 이 시간을 중점으로 해결해야 함으로 다익스트라 라는 최단경로를 구하는 알고리즘으로 해결하였다.

 

처음써보는 알고리즘이라 생소했는데 큰 틀은 이렇다.

1. 출발 노드를 설정하고 (0,start)

2. 출발노드 제외 최단거리 테이블을 '무한'으로 초기화 한다. (distance = [INF] * (n+1))

3. 방문하지 않은 노드중 최단거리가 가장 짧은 노드를 선택한다.

- 선택된 노드까지의 최단 거리는 확정된다.

4. 선택된 노드를 거쳐 다른 노드로 가는 시간을 계산하여 최단 거리 테이블과 비교, 갱신한다.

5. 3~4의 과정을 반복한다.

 

여기서 시간초과를 내지 않기 위해 heapq(최소힙)을 사용하여 최단거리 정보를 담아 출발 노드로부터 가장 짧은 노드를 빠르게 찾을 수 있게한다.

만약 heap을 사용하지 않으면 매번 최단거리가 가장  짧은 노드를 순차적으로 탐색해야한다.

 

마지막으로 이 간선은 단방향임으로 갈때와 올때의 시간을 따로 구해주어야한다.

n의 노드에서 파티가 열리는 노드까지 가는 최단거리와

파티가 열리는 노드에서 n의 노드까지의 최단거리의 합 중 가장 긴 거리를 출력해주면 된다.

 

---

아직 다익스트라 문제가 처음이라 조금 생소하지만 여러번 연습 해봐야겠다.