정글사관학교 24일차 TIL: 다익스트라 알고리즘, 최소비용 구하기(#1916)

0. 목차

1. 다익스트라 알고리즘

2. 최소비용 구하기(#1916)

 

1. 다익스트라 알고리즘

다익스트라 알고리즘은 DP를 이용한 대표적인 최단경로 알고리즘이다. 특정한 하나의 노드(출발점을 고정)에서 다른 모든 노드로 가는 최단 경로를 알려주는 알고리즘이다. 다익스트라 알고리즘의 핵심 개념만 요약정리하면

 

• 우선순위 큐(Heap)을 사용한다는 점 (최소 비용을 뽑아내기 위해)
• 이차원 배열에 값을 미리 저장(DP)해둔다는 점(그때그때 최단 경로/최소 비용 등 최솟값을 배열에 저장해두고 갱신하는 식으로)
• 다익스트라에서 음의 간선은 포함할 수 없다는 점 (음의 간선까지 고려 가능한 알고리즘은 벨만포드가 있다는데 이번에는 쓸일이 없어서 패스)

다익스트라와 DP

다익스트라 알고리즘은 하나의 최단거리를 구할 때 그 이전까지 구했던 최단거리 정보를 그대로 가져와서 사용한다. 어디서 많이 봤던 개념이지 않나? 바로 DP와 같다. (DP 관련 개념 정리는 여기에) 그 이전까지 구했던 최단거리 정보를 가져와서 쌓으니 가장 작은 애들을 오름차순으로 정렬해서 얘네를 가져와서 쓰는 식.

 

다익스트라 작동과정

1. 출발 노드를 설정한다. (다익스트라는 출발점을 고정하고 그 출발점을 기준으로 다른 각각 노드에 대한 최단경로를 제공한다.)
2. 출발 노드를 기준으로 인접한 노드의 최소 비용을 저장한다. (이때, 비용은 이차원 배열에 저장한다.)
3. 방문하지 않았던 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신한다.
5. 위 과정에서 3-4를 계속 반복한다.

백문이 불여일견이라고, 아래에서 문제를 하나 풀어보도록 하자.

 

2. 최소비용 구하기(#1916 with Python)

문제 링크는 여기. 이 문제는 골드 5 난이도이다(빡세다..)

 

위에서 설명했듯 이 문제는 최단 경로를 힙으로 저장해서 그때그떄 최단경로를 이차원 배열에 배치하는 식으로 업데이트한다. 문제에서 입력값부터 받아오자. 문제에서는 시작 도시, 도착 도시, 그리고 직통 경로로 가는데 드는 비용을 제공한다. 이때 우리는 출발 도시에서 도착 도시로 가는데 드는 비용을 저장할 이차원 배열 cost_graph를 생성한다. cost_graph의 인덱스 값을 출발 노드의 번호로, 도착점과 그에 대한 비용을 리스트로 만들어서 해당 인덱스의 value로 배치한다.

 

리스트에 값을 저장할 때 cost를 리스트의 앞에 배치하는데, 이는 뒤의 다익스트라 함수에서 힙을 이용할 때 최솟값을 기준으로 heappop을 하기 위함이다.

 

n = int(stdin.readline())
m = int(stdin.readline())
cost_graph = [[] for _ in range(n+1)]

for i in range(m):
    start, end, cost = map(int, stdin.readline().split())
    cost_graph[start].append([cost, end]) # 2차원 배열이 아니라 1차원에다가 끝점을 배치 => 단방향 그래프이기 때문.

start_city, end_city = map(int, stdin.readline().split())

 

다음은 다익스트라 함수를 짜보자. 주어진 cost보다 새로운 경로를 추가해서 나오는 경로 길이가 짧다면 그 값을 c에 추가하고 heap에 push한다. 최종적으로 dist[end]를 return한다.

 

def dijkstra(n, start, end, cost_graph): # start: 출발 도시 / end: 도착 도시 / cost_graph: 비용 그래프
    q = []
    dist = [inf] * (n+1) # 시작점에서 각 점까지의 거리
    dist[start] = 0 # 출발점 기준 자신에서 자기까지 거리는 0
    heapq.heappush(q, [0, start]) # 자신부터 출발하니 [0, start]을 집어넣는다.
    
    while q:
        cos, pos = heapq.heappop(q) # 최소 비용인 애 뽑아냄 (pos: 해당 시점에서 출발점 & cos: 그때까지의 누적 최소 비용)
        if cos > dist[pos]:
            continue
        
        for c, p in cost_graph[pos]: # cost_graph에서 pos(시작점)과 연결된 끝점(p)& 그에 드는 비용(c)을 뽑아서
            c += cos # 그 비용에다가 원래 시작점 비용을 더해준다. (비용 누적시킴)
            if c < dist[p]: #시작점에서 p점까지 거리가 c보다 크다면
                dist[p] = c
                heapq.heappush(q, [c, p])
    
    return dist[end]