[백준]1753 최단경로(Python)

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

1753번: 최단경로

 

문제 접근 

 

다익스트라 알고리즘이 무엇인지 모르기에 우선 공부한다는 생각으로 접근 

 

*다익스트라(Dijkstra): 시작점으로부터 나머지 정점까지 최단거리를 구할 때(=>요 문제)

cf) 플로이드 워셜: 각 정점 간 최단경로를 구할 때 

 

원리

매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘과 구분

1. 출발 노드를 설정

2. 최단 거리 테이블 초기화

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

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신

5. 3, 4 과정 반복

 

코드

1. 처음 테이블은 시작점인 1을 기준으로 만든다.

	1	2	3	4	5
start(1)	0	2	3	INF	INF

 

2. 현재 테이블 기준으로 자기 자신(1)을 제외한 가장 가까운 정점(2)를 선택하여 테이블을 갱신한다. 

3. 1과 마찬가지로 2번 정점에서 갈 수 있는 정점을 조사한다.  그리고 그 중 최소 힙에서 가장 가중치가 적은 노드(2->4)를 선택한다.

    2->3 (4): 1->2->3 (2+4 = 6)

                      1->3 (3)  이므로 테이블을 갱신하지 않고 다음 단계를 진행한다. 

    2->4 (5): 1->2->4 (2+5 =7)

                      1->4 (INF)이므로 7 < INF이므로 테이블을 업데이트 

4. 이어서 탐색할 필요가 있는 노드라고 판단하여 최소 힙에 넣어준다. 

 

힙(heap)을 이용한 다익스트라 알고리즘

힙 없이 구현하면 매번 최단 거리가 가장 짧은 노드를 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야 한다. 힙 자료구조를 이용하게 되면, 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로 출발 노드부터 가장 거리가 짧은 노드를 더 빠르게 찾을 수 있다. 

* 힙(heap): 우선순위 큐 기능 구현 가능, heapq 라이브러리 제공(python의 힙은 최소 힙으로 구성)

 

시간 복잡도

1. 힙에 정점 추가하고 제거하는 작업은 O(logV)

2. 각 정점은 최대 한 번씩 힙에 추가되므로 힙 연산은 총 V번 

3. 각 정점에 대해 모든 인접한 간선을 검사하는 것도 E번 

4. 간선이 힙에 추가되는 작업은 최악의 경우 각 간선마다 한 번씩 발생하므로 E번

=> O((V+E)logV)지만 힙연산이 지배적이므로 O(ElogV)

 

코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

# 정점, 간선의 개수
V, E = map(int, input().split())

# 시작 정점
K = int(input())

# 가중치 테이블 dp => 시작 노드에서 각 노드로 가는 현재까지 알려진 가장 짧은 경로의 길이 저장!
dp = [INF] * (V+1)
heap = []
graph = [[] for _ in range(V+1)]

def Dijkstra(start):
    dp[start] = 0   # 시작 정점에 해당하는 가중치를 0으로 초기화
    heapq.heappush(heap, (0, start))    # 튜플에서 첫 번째 값은 우선순위

    while heap: # 힙에 원소가 없을 때까지 반복
        wei, now = heapq. heappop(heap)

        if dp[now] < wei:
            # 힙에서 pop한 노드의 가중치와 현재 테이블의 가중치와 비교한 후 더 가중치가 큰 튜플이면 무시
            continue

        for w, next_node in graph[now]: # 현재 노드와 연결된 모든 노드에 대해 반복
            next_wei = w + wei

            if next_wei < dp[next_node]:    # 계산한 총 가중치(next_wei)가 현재 알려진 다음 노드까지의 가중치보다 작은지 확인
                dp[next_node] = next_wei    # 만약 짧다면 갱신
                heapq.heappush(heap, (next_wei, next_node)) # 힙에 push


for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u]. append((w,v)) # (가중치, 목적지) 형태로 저장


Dijkstra(K)
for i in range(1, V+1):
    if dp[i] == INF:
        print("INF")
    else:
        print(dp[i])

 

문제 회고

 

23/01/13

사실 잘 이해가 안간다..

시험 보고 와서 멍... 내일 코테 끝나고 다시 봐야겠다ㅠㅠ

 

23/01/14

지이이잉ㄴ짜 오래 봤더니 이해가 조금 된다!

확실히 최소힙의 기본 개념이 잡혀야지 다익스트라 알고리즘을 제대로 이해할 수 있는 것 같다.

사실 튜플이라는 자료 구조를 제대로 사용한 적도 처음이라서 문제 풀이가 낯설었던 것 같다.

계속 반복해서 하면 익숙해지겠지..?