우선순위 큐 다익스트라

우선순위 큐

• heapq 라이브러리를 활용해서 우선순위 큐 사용 가능.
• 데이터가 리스트 형태일 경우, 0번 인덱스를 우선순위로 인지, 우선순위가 낮은 순서대로 pop 할 수 있음!!

import heapq

queue = []

heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'D'])
print (queue)
//[[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']]

for index in range(len(queue)):
    print (heapq.heappop(queue))
    
//[1, 'C']
//[2, 'A']
//[5, 'B']
//[7, 'D']

---

다익스트라

• 단일 출발 최단경로 문제
• 그래프 내 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제

 

1. 출발지를 s로 정하고, 다음과 같이 표시한다.
      (s,    t,     x,     y,     z  순)
거리 = [0,    inf,   inf,   inf,   inf]
방문 = [True, False, False, False, False]

2. 갈 수 있는 노드들의 최소거리를 측정한다.
s->t: 10
s->y: 5
      (s,    t,     x,     y,     z  순)
거리 = [0,    10,    inf,   5,     inf]
방문 = [True, False, False, False, False]

3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다.
y->t: 3
y->x: 9
y->z: 2
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     14,    5,    7]
방문 = [True, False, False, True, False]

4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다.
z->x: 6
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     13,    5,    7]
방문 = [True, False, False, True, True]

5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다.
t->x: 1
t->y: 2
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, False, True, True]

6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다.
x->z: 4
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True]

7. 방문 안한 노드가 없으므로 끝낸다.
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True]

---

Logic

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단거리를 갱신하는 기법
• BFS와 유사하다.

---

우선순위 큐를 활용한 다익스트라 알고리즘.

• MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 깨낸다.

1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장한다.

• 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함(inf라고 표현함)
• 우선순위 큐에 (첫 정점, 거리0)만 먼저 넣는다.

2) 우선 순위 큐에서 노드를 꺼낸다.

• 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
• 첫 정점이 인접한 노드를 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점가지의 거리를 비교한다. 
• 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
  • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문한다.
  • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴거리를 가진 경우에는 해당 노드와 인접한 노드간의 거리를 계산하지 않는다!
• 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.

3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

• 업데이트 된 것이 없을 때까지 반복!

---

import headq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    #우선순위 큐
    heapq.heappush(queue, [distances[start], start])

    while queue:
        # current_distance = 현재 노드까지 이르는데 누적된 거리(비용)
        current_distance, current_node = heapq.heappop(queue)

        # 이미 노드에 이르는 최솟값보다 현재 누적 값이 크면 가망이 없으므로 continue
        # 나의 노드를 기준으로 이미 최솟값 측정이 끝났다는 의미는 그 노드가 방문처리가 되엇다는 의미!
        # 나의 지금 누적 값이 이미 기록된 최소 비용보다 크다면 visited 했단는 의미!
        # 위의 예시에서 큐에 (b,8)이 이미 있는데 (b,6)으로 갱신이 되어 들어오면
        # (b,8)은 볼 필요가 없음!
        if distances[current_node] < current_distance:
            continue

        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
    return distances

mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

dijkstra(mygraph, 'A')
// {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

---

이차원 배열 다익스트라

당신은 화성 탐사 기계를 개발하는 프로그래머입니다.
그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 타사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다.
화성 탐사 기계가 존재하는 공간은 N*N 크기의 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재합니다.
가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요.
화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다

입력 조건

첫째 줄에 테스크 케이스의 수 T( 1 <= T <= 10)가 주어집니다.
매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어집니다. (2 <= N <= 125)
이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분합니다 (0<= 각 칸의 비용<=9)
출력 조건 각 테이스트 케이스마다 [0]의 위치에서 [N - 1][N - 1]의 위치로 이동하는 최소 비용을 한 줄에 하나씩 출력합니다.

입력 예시
3
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4

출력 예시
20
19
36

import sys
import heapq

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
T = int(sys.stdin.readline())


def dijkstra(graph):
    N = len(graph)
    distance = [[float('inf')] * N for _ in range(N)]
    distance[0][0] = graph[0][0]
    queue = []
    # 이부분 주목!!
    heapq.heappush(queue, [distance[0][0], 0, 0])
    while queue:
        acc, x, y = heapq.heappop(queue)
        if acc > distance[x][y]:
            continue
        for i in range(4):
            x_ = x + dx[i]
            y_ = y + dy[i]
            if 0 <= x_ < N and 0 <= y_ < N:
                cur = graph[x_][y_] + distance[x][y]
                if cur < distance[x_][y_]:
                    distance[x_][y_] = cur
                    heapq.heappush(queue, [cur, x_, y_])
    return distance[N-1][N-1]
for _ in range(T):
    N = int(sys.stdin.readline())
    graph = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
    print(dijkstra(graph))