얼렁뚱땅 개발 일지

import sys
import heapq

input_value = sys.stdin.read().splitlines()

arr = []

# 도시 갯수
N = int(input_value[0])

# 버스 갯수
M = int(input_value[1])

start, end = map(int, list(input_value[-1:][0].split()))

graph = [[] for _ in range(N + 1)]

for i in input_value[2:-1]:
    a, b, weight = map(int, i.split())
    graph[a].append([b, weight])

def dijkstra(graph, start):
    distance = {node : float('inf') for node in range(len(graph))}
    distance[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        cur_dist, cur_node = heapq.heappop(priority_queue)
        
        if cur_dist > distance[cur_node]:
            continue

        for node, w in graph[cur_node]:
            dist = cur_dist + w
            if dist < distance[node]:
                distance[node] = dist
                heapq.heappush(priority_queue, (dist, node))
    return distance
    
print(dijkstra(graph=graph, start=start)[end])

다익스트라 알고리즘

간선에 거리가 있을 때 목적지에서 도착지까지 최소의 거리를 가지고 가는 경로를 구하기 or 최소 거리 구하기

1. 거리에 대한 배열 선언 : minimum 비교로 inf값을 가지는 배열 선언

2. 시작은 거리가 0이니 0으로 선언 후 시작

3. 우선 순위 큐에 거리와 현재 node를 입력할 수 있도록 init

4. 우선 순위 큐에 들어 있는 거리와 node를 pop하여 비우고, 현재 거리와 node로 씀

5. 거리가 현재 노드보다 크다? -> start 노드가 아닌걸로 판단하여 continue

6. 그래프에 있는 거리와 node를 가지고 연산 진행

그래프는 머리 아픈거 같다 히히..

우선 순위 큐를 활용한 중간 값을 구하는 방식이 있어 저장해본다.

해당 방식은 최소힙과 최대힙을 활용하여 중간값을 구한다.

이러한 방식은 기본적인 탐색보다 빠른 시간 복잡도를 가진다. 전체 입력을 받은 뒤O(n log n)의 복잡도로 매우 빠르다.

# 우선 순위 큐에서 중간 값을 찾기 위해서는 최대 힙, 최소 힙 사용
# 최대 힙에는 중간값 이하의 값을, 최소 힙에는 중간값 초과의 값을 넣기
def add_num(num):
    if not max_heap or num <= -max_heap[0]:
        heapq.heappush(max_heap, -num)
    else:
        heapq.heappush(min_heap, num)
        
    if len(max_heap) < len(min_heap):
        heapq.heappush(max_heap, -heapq.heappop(min_heap))
    elif len(max_heap) > len(min_heap) +1:
        heapq.heappush(min_heap, -heapq.heappop(max_heap))