[골드 V] 1753번. 최단경로

 문제 

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

1753번: 최단경로

 사용 언어 

Python3

 풀이 과정 

며칠 전에 공부한 다익스트라 알고리즘의 기본 문제를 풀어보았다.

float('inf')를 print( )하면 inf로 잘 뜨길래 그대로 제출했는데 처음에 틀렸습니다가 떴길래 문제를 다시 읽으니 출력 형식이 inf가 아닌 INF였다.

print(*distance[1:], sep='\n')

그래서 삼항 연산자로 바꿔서 출력하는 부분을 추가했더니 맞았습니다!!

 

 제출 답안 

import heapq
from sys import stdin, maxsize
input = stdin.readline
INF = maxsize

node, line = map(int, input().split())
startNode = int(input())
graph = [[] for _ in range(node+1)]
for _ in range(line):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))
distance = [INF for _ in range(node+1)]

queue = []
def dijkstra(startNode):
    heapq.heappush(queue, (0, startNode)) # 시작점은 거리 0
    distance[startNode] = 0
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for next in graph[node]:
            # next는 (end, cost)로 append 해놓은 정보
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue, (cost, next[0]))

dijkstra(startNode)
for i in range(1, node+1):
    print("INF" if distance[i] == INF else distance[i])

 

 공부한 내용 

heapq

기존의 다익스트라 알고리즘의 문제점 중 하나는 알고리즘 반복 단계에서 시작 노드와 가장 거리가 짧은 최단 거리 노드를 찾아야 하는데, 이 때 매번 선형탐색을 수행했어야 했다는 것이다. 

 

이러한 문제를 우선순위 큐를 이용해 해결할 수 있다. 우선순위 큐는 힙이라는 자료구조로 구현할 수 있는데, 가장 우선순위가 높은 데이터부터 Out(삭제)되는 방식을 취한다. 따라서 우선순위 큐는 데이터를 특정한 우선순위에 따라 처리하고 싶을 때 자주 사용된다. (우선순위 큐를 리스트로도 구현할 수 있지만, 최악의 경우 삭제 시 시간복잡도 O(N)이 걸리는 반면 힙을 사용하면 최악 경우라도 삭제 시 시간 복잡도 O(logN)이 걸린다)

 

우선순위 큐를 구현하는 여러가지 프로그래밍 언어의 라이브러리들은 최소 힙 또는 최대 힙을 구현한다. 최소 힙이란, 데이터의 값이 가장 낮은 것을 가장 우선으로 여겨 정렬하는 반면 최대 힙은 데이터의 값이 가장 큰 것을 가장 우선으로 여겨 정렬하게 된다. Python에서 제공하는 라이브러리들은 최소 힙 방식으로 제공된다.

 

이제 우선순위 큐를 다익스트라 알고리즘에 어떻게 사용하는지 살펴보자. 다익스트라 알고리즘에서 우선순위 가준은 뭘까? 바로 시작 노드와의 거리가 가장 가까운 노드를 의미한다. 따라서 알고리즘을 반복할 때마다 실시간으로 시작노드와 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 활용한다.

 

참고로 기존의 간단한 다익스트라 알고리즘을 구현할 때는 사전에 2가지 종류의 리스트를 먼저 정의하고 진행했다. 첫 번째는 최단 거리를 기록하면서 갱신할 거리 테이블, 두 번째는 방문한 노드인지 처리하고 확인하는 목적의 방문 테이블이였다. 하지만 우선순위 큐를 이용하게 되면 최단 거리를 기록할 거리 테이블만 정의한다. 왜냐하면 우선순위 큐를 이용하게 되면 우선순위 큐가 알아서 가장 최단 거리인 노드를 가장 앞으로 정렬해주기 때문에 기존에 기록한 최단 거리보다 크다면 그냥 무시해주면 된다. 만약 기존에 기록한 최단 거리보다 더 짧은 새로운 최단 거리가 등장하게 되면 해당 거리와 노드를 우선순위 큐에 넣어준다.

 

더 자세한 내용은 출처를 참고하고 힙을 사용하는 방법을 알아보자.

 

1. 힙에 원소 추가

heap = []
heapq.heappush(heap, 4)

2. 힙에서 원소 삭제 : 가장 작은 원소를 삭제 후 그 값을 리턴

heapq.heappop(heap)

3. 최소값 삭제하지 않고 얻기 : 주의사항은 인덱스 0에 가장 작은 원소가 있다고 해서, 인덱스 1에 두 번째 작은 원소, 인덱스 2에 세 번째 작은 원소가 있다는 보장은 없다는 점

print(heap[0])

4. 기존 리스트를 힙으로 변환

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap) # [1, 3, 5, 4, 8, 7]

 

출처: https://techblog-history-younghunjo1.tistory.com/248?category=1014800 | https://www.daleseo.com/python-heapq/

 

 코드 개선 

1. 나는 최대값을 표현하기 위해 저번에 공부한 float('inf')를 계속 사용했는데,  맞힌 사람 을 보니 대신  sys.maxsize 를 사용하는 사람이 많아서 바꿔보았다.

➡ 시간은 똑같은데 메모리가 꽤 줄어들었다. 앞으로는 sys.maxsize를 대신 써봐야겠다.