[알고 스터디] 7. 최단 경로 알고리즘 - 1916

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

1916번: 최소비용 구하기

---

[1] 풀이 및 생각

이 문제 진짜 단순한데 풀면서 너무너무너무너무 암걸릴뻔했다.

왜냐? 유방향 그래프인데 무방향인줄 앎,,

그래서 답이 계속 틀려서 너무 ,,,, 지쳤다,,,,,

 

문제 자체는 다익스트라만 구현하면 돼서 단순하고 최단거리 입문용인데 진짜 하,, 저거때매 넘 힘들었다.

난 내가 뭘 틀렸는지 진짜 진지하게 겁나 고민했다. 분명 알고리즘 구현자체는 똑같은데,,ㅠㅠ

 

다익스트라 알고리즘은 최단 거리를 구하는 알고리즘으로,

시작하는 노드와 끝 노드가 있다고 했을 때,

시작점-끝점의 거리 리스트를 구현해서

인근 노드의 거리를 조사하며 거리 리스트를 최소로 업데이트한다.

그래서 처음엔 inf로 설정하고 현재 노드의 인근 노드 중 거리가 가장 가까운 노드부터 가져와보면서 업데이트한다.

 

1) 기본적인 다익스트라: 그냥 리스트에 담아서 작은거 순회해서 찾아가면서 뽑기

2) 향상된 다익스트라: heap을 통해서 거리값이 작은걸 먼저 뽑기

<이부분 다시봐야할듯>

[2] 코드

import sys
import math
import heapq

def dijkstra(distance, graph, root, end2):
    queue = []
    distance[root] = 0
    heapq.heappush(queue, [distance[root], root])

    while queue:
        cur_dis, end = heapq.heappop(queue)
        if end == end2: return distance

        if distance[end] < cur_dis:
            continue
        for new_dis, new_des in graph[end]:
            dist = cur_dis + new_dis
            if distance[new_des] > dist:
                distance[new_des] = dist
                heapq.heappush(queue, [dist, new_des])

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = []
distance = [math.inf] * (n+1)

for i in range(n+1):
    graph.append([])

for _ in range(m):
    s, e, v = map(int, sys.stdin.readline().split())
    graph[s].append([v, e])

ans_s, ans_e = map(int, sys.stdin.readline().split())
dis_list = dijkstra(distance, graph, ans_s, ans_e)
print(dis_list[ans_e])

 

[3] 시간복잡도 계산

 

다익스트라 알고리즘을 향상된 버전으로 heap 구현을 했기 때문에 O(V + E) * log V (V: 노드수, E: 간선 수)