[BOJ][Python]1916 풀이

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

1916번: 최소비용 구하기

import heapq
import sys
ssr = sys.stdin.readline
INF = 100000000

def dijkstra(start, arrive):
    min_cost = [INF for _ in range(n+1)]
    h = []
    heapq.heappush(h, (0, start)) # 거리, 도착 순서
    min_cost[start] = 0
    while h:
        now_cost, now = heapq.heappop(h) # 거리, 도착 순서
        if now_cost > min_cost[now]:
            continue
        for after_cost, after in bus[now]:
            if min_cost[now]+after_cost < min_cost[after]:
                min_cost[after] = min_cost[now] + after_cost
                heapq.heappush(h, (min_cost[after], after))
    print(min_cost[arrive])

n = int(ssr())
m = int(ssr())
bus = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, ssr().split())
    bus[a].append((c, b))
start, arrive = map(int, ssr().split())
dijkstra(start, arrive)

//추가

데이크스트라 알고리즘에 대해서 정리를 해보았습니다. 데이크스트라 알고리즘에 대해서 좀 더 알고 싶은 분은 아래의 링크에서 데이크스트라에 대해 좀 자세하게 볼 수 있습니다.

https://justduke.tistory.com/356

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

 

이 문제는 정말 오래전부터 잡고 있었던 문제입니다. 도저히 데이크스트라 알고리즘이 이해가 안 되어서 방치해 뒀다가 기억이 나면 또 좀 시도해 보고 개념 공부를 해보고, 또 좀 시도해 보고 개념 공부를 해보고 한 게 제 생각엔 거의 1년이 다 되어 가는 것 같아요. 물론 알고리즘 문제만 잡고 사는 게 아니다 보니(블로그 포스팅은 알고리즘 문제 풀이가 주이긴 합니다만...) 다른 일을 한다고 알고리즘 문제 자체를 안푸는 시기도 있었고요. 처음 이 문제의 풀이를 제출했던 게 11개월 전입니다. 그때는 bfs로 풀었는데 시간초과가 났었네요. 오늘이 되어서 갑자기 제 머리가 좋아진 건지 이때까지 그래도 틈틈이 데이크스트라 공부를 했던 게 도움이 된 건지 오늘따라 이해가 잘 되어서 이렇게 코드를 작성할 수 있게 되었습니다. 앓던 이가 빠진 것 같아 속이 다 시원하네요.

 

위와는 별개로 오늘 문제를 풀면서 정말 뼈에 사무치도록 변수명을 잘, 눈에 띄게, 구분이 되게 지어야 한다는 점을 느꼈습니다. 보통 변수명을 생각하는게 굉장히 귀찮은 작업이기에 간단한 코드의 경우는 지역변수는 이름이 중복되는 게 예사고 전역변수도 자주 쓰면서 변수명을 알파벳 하나로 해버린다든가 하는 경우가 정말 많았습니다. 제가 이때까지 풀어왔던 문제들이 그다지 코드가 길거나 어렵지 않았던 점도 물론 작용했겠습니다만, 오늘은 정말 된통 당했습니다. 평소처럼 i로 범벅이 되어있는 상황에서 데이크스트라를 적용해 본다고 코드의 변경이 지속적으로 일어나다 보니 여기 i가 어디 i인지 i의 인덱스로 호출하는 원소들은 뭔지, 거기다 heapq 모듈을 사용하려고 버스 가격과 도착지의 위치도 변경하다 보니 머릿속에서 뒤죽박죽 섞여서 코드를 틀리게 짜놓고 운 좋게 예제를 통과하니까 이상한 부분만 고치면서 온통 시간 낭비를 했습니다. 결국 문제는 힙에 추가하는 과정에서 현재 위치의 최소가격을 넣어야 하는데 그냥 현재 위치로 오는 가격을 넣었더라고요. 다시는 변수명을 대충 짓지 않겠다고 결심했습니다.

 

이 문제는 가장 기본적인 데이크스트라 문제입니다. 데이크스트라 또는 다익스트라 최단거리 알고리즘이라고 부르는데요. 영어식으로 읽으면 다익스트라, 네덜란드식으로 읽으면 데이크스트라라고 하네요. 축구선수중에 반 다이크라는 선수 있잖아요. 그분도 네덜란드 사람이라 번역에 따라 판데이크나 반 다이크 둘 중에 하나로 표기되어 있는 경우를 볼 수 있습니다. 아무튼 그래서 데이크스트라든 다익스트라든 같은 것을 뜻하기 때문에 편하신 대로 부르시면 됩니다. 저는 원래 데이크스트라가 맞는 거라고 하니 데이크스트라라고 부르겠습니다.

 

데이크스트라 최단거리 알고리즘을 사용하는 그래프 문제의 경우 간선에 대한 가중치가 주어지고 해당 가중치는 음수가 아니어야 한다고 합니다. 이외에도 최단거리 알고리즘에 플로이드 워셜, 벨만 포드 등이 있습니다. 간단하게 짚고 넘어가면 플로이드 워셜은 음수도 가능하고, 벨만 포드는 음수에 사이클이 있어도 가능하다고 합니다(다음에 자세하게 소개를 드릴 수 있으면 좋겠네요). 그래서 데이크스트라는 실생활에서도 자주 쓰이는 최단거리 알고리즘이라고 합니다(현실에는 음의 간선이 존재하지 않으니까요. 내비게이션등에 사용된다고 합니다).

 

그래서 문제 설명을 좀 하자면 도시의 갯수와 버스 노선의 개수, 노선 정보가 나온 다음 마지막으로 시작 도시와 마지막 도시를 주고 시작 도시에서 마지막 도시까지 가는 데에 드는 최소 비용을 출력하는 게 해당 문제가 요구하는 사항입니다. 해당 문제는 데이크스트라로만 풀 수 있도록 일부러 시간제한을 타이트하게 설정했습니다(고수분들이 오래 걸리는 알고리즘으로 푼 다음에 시간을 더 줄여야 한다고 제보를 하시더라고요). 데이크스트라 알고리즘의 과정을 말로 설명해 보면,

1. 시작 노드를 정합니다.

2. 시작 노드에서 다른 노드로 갈 때 걸리는 비용(길이) 테이블을 초기화합니다.

3. 아직 방문하지 않은 노드 중에서 가장 비용이 적은(길이가 짧은) 노드부터 방문합니다(방문하면서 최소 테이블을 갱신합니다).

4. 더 이상 방문하지 않은 노드가 없어질 때까지 3번을 반복합니다.

사실 해당 설명이 전부인데 저는 처음에 데이크스트라를 공부할 땐 이게 그렇게 안 와닿더라고요. 많은 블로그나 유튜브 강의를 참고했었는데 개인적으로 이것이 코딩 테스트다 with 파이썬(나동빈 저)을 추천합니다. 금액은 3만 원이 넘긴 하는데 은근히 잘 읽히고 예제코드도 깃허브에서 찾아볼 수 있기 때문에 혹시 알고리즘 독학을 하고 계시다면 추천드립니다. 문제도 백준 문제들로 알려줘서 백준으로 독학하는 분들은 입출력이나 문제 느낌이 익숙하실 거예요.

 

위에서 적었던 설명을 바탕으로 해당 문제를 풀어보면 마지막 줄에 시작 노드와 마지막 노드를 주니까 일단 시작 노드 설정은 쉽게 할 수 있습니다. 다음으로는 최솟값을 구하는 게 목적이니까 테이블을 초기화할 때 해당 문제에서 나올 수 없는 큰 수(노드는 1000까지이고 금액이 100000까지니까 1000*100000이 최댓값이 되겠네요)로 테이블을 초기화해주시면 됩니다. 그리고 시작노드는 버스가 필요 없으니까 0으로 값을 바꿔줍니다.

 

그리고 가장 중요한 '3번. 아직 방문하지 않은 노드 중에서 가장 비용이 적은 노드부터 방문합니다.'입니다. 이 부분을 신경 쓰지 않으면 방문처리에 따라 나중에 최솟값이 나오더라도 제대로 갱신을 하지 못하거나 불필요한 계산을 하게 되기도 하니까 해당 부분을 구현하는 것을 잊지 말아 주세요. 그리고 이 부분을 위해서 우선순위큐를 사용합니다.

 

파이썬에서는 heapq나 PriorityQueue 라이브러리를 사용해서 우선순위큐를 구현할 수 있습니다. 아마 solved.ac의 클래스별 문제를 풀어오신 분들은 이미 최소 힙, 최대 힙등의 문제를 풀어보시면서 heapq 라이브러리를 이미 사용해 보셨을 텐데요. 기본적으로 파이썬의 heapq는 최소 힙을 지원하기 때문에 지금처럼 최솟값을 구할 때 편하겠죠. 혹시 우선순위큐가 무엇인지 모르는 분들을 위해 간단하게 설명을 하자면 큐인데 가장 먼저 들어온 원소가 먼저 나가는 게 아닌 우선순위가 높은 원소가 먼저 나가는 큐를 우선순위 큐라고 합니다. 그러면 이런 경우는 가장 비용이 적은 게 우선순위가 높도록 설정하면 제일 먼저 방문하도록 짤 수 있겠죠.

 

우선순위큐는 그래서 저장할 때부터 우선순위가 높은 게 가장 먼저 나갈 수 있도록 저장(첫번째 원소를 기준으로 판단하기 때문에 가격을 먼저 저장)을 합니다. 그래서 힙의 특징을 사용하는 것이고요. 힙은 부모노드가 항상 자식노드보다 작거나 큰 형태를 하는 이진트리 이므로 우선순위가 높은 자료를 저장할 때 선형시간이 아닌 로그시간이 걸리는 것이죠. 그렇게 해서 탐색시간을 줄이는 것에서 이점을 볼 수 있는 구조를 갖고 있습니다. 다만 주의해야 하는 점으로 자식 노드 간의 크기도 작은 순서로 정렬되어 있다고 보장을 못하기 때문에 가장 우선순위가 높은 하나에 대해서만 사용할 수 있다고 알아두셔야 합니다.

 

그래서 이런 특징 때문에 가장 작은 것을 우선순위가 높도록 하면 굳이 min을 이용해서 O(N)의 시간복잡도를 가질 필요 없이 O(logN)으로 최소 비용을 찾아서 해당 노드로 갈 수 있는 것이죠. 그러면 이제 계속 그 과정을 반복하면 끝입니다. 최소 비용이 드는 노드로 가서 해당 노드를 방문처리하고 해당 노드에서 또 최소 비용으로 갈 수 있는 노드를 찾고 방문처리하고... 를 반복하면서 테이블을 갱신하다가 모든 노드에 대해서 방문처리가 되었다면 코드는 종료되고 도착지의 최소 비용을 출력하게 됩니다.

 

데이크스트라 알고리즘의 이해를 위해 알아둬야 하는 사전 지식들이 많아서 상당히 풀이가 난잡해 보일 수 있습니다. 그래서 데이크스트라 공부가 하고 싶은 분들을 위해 정리를 좀 해보자면,

1. 그래프 탐색에 대한 이해

2. 데이크스트라 알고리즘의 개념과 그 과정

선택 1. 우선순위큐에 대한 이해

선택 2. 힙에 대한 이해

이 정도가 필요할 것으로 생각합니다. 먼저 그래프 탐색에 대한 내용을 알고 계시는 게 좋을 것 같습니다. 큐를 사용하는 bfs에 대해서 알고 계시는 편이 확실히 감을 빨리 잡을 수 있게 도와줄 겁니다. 그 이후에 데이크스트라 알고리즘이 무엇인지, 이것을 왜 사용하는지, 어떤 과정으로 진행되는지를 알아두고 가장 비용이 적은 노드를 효율적으로 찾기 위해 우선순위큐를 이용한다는 점, 우선순위큐가 보통 힙으로 구현된다는 점에 대해 알아두신다면 그래서 우선순위큐를 사용하는구나, 핵심은 좀 더 빨리 최소 비용 루트를 찾으려는 거였구나를 알게 되실 겁니다.

 

시간제한이 넉넉하다면 아마 우선순위큐를 사용하지 않아도 통과하겠지만, 좋은 게 있는데 굳이 안 써야 할 이유도 없으니 이참에 heapq 라이브러리를 사용해 보는 것을 추천합니다.