[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

 

네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다.

 

플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터는 두지 않았습니다.

 

맨날 보던 그래프만 또 보면 지겨울까봐 이번에는 조금 다른 모양의 방향 그래프를 준비했습니다. 다익스트라 알고리즘은 방향 그래프 혹은 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘입니다. 시작점은 당연히 아무 정점이나 잡아도 되지만 제 마음대로 1번 정점을 시작점으로 잡겠습니다. 이 때 1번 정점에서 다른 정점들까지 가는 최단 거리를 표에 썼고, 다익스트라 알고리즘을 돌리면 저 표의 값들을 채울 수 있습니다.

 

플로이드 알고리즘을 다시 떠올려보면 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘인 반면 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다. 그래서 어떻게 보면 기능은 플로이드가 더 좋은데 당연히 다익스트라가 플로이드보다 뭔가 효율적인게 있으니까 플로이드 알고리즘 말고도 다익스트라 알고리즘을 별도로 배웁니다.

 

단, 플로이드 알고리즘은 음수인 간선이 있는건 상관이 없고 음수인 사이클이 있을 때에만 문제가 발생했지만 다익스트라 알고리즘은 음수의 가중치를 가지는 간선이 있으면 아예 사용을 할 수가 없습니다. 음수인 간선이 있는데 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하고 싶다면 벨만포드 알고리즘이란걸 쓰면 되긴 하지만 이 강의에서는 다루지 않을 내용이라 대회까지 염두에 두시는 분이라면 별도로 공부를 하셔도 됩니다. 그렇지 않다면 굳이 벨만포드까지 알아볼 필요는 없습니다.

 

다익스트라 알고리즘은 학부 알고리즘 수업에서 반드시 다루는 알고리즘이기도 하고 네트워크 같은 데에서 쓰이기도 하기 때문에 적어도 이름과 그 목적만큼은 꽤 유명합니다. 그런데 구현에서 실수를 할 수 있는 여지가 굉장히 많아서 다익스트라 알고리즘에 대해 어렴풋이 알고만 있고 구현에 자신이 없다면 이번 기회에 확실하게 익혀보도록 하겠습니다.

 

참고로 길찾기 알고리즘의 대표적인 예시로 A*(A star) 알고리즘이라는 것을 들어본 적이 있는 분도 계실 것 같습니다. BOJ에서 길찾기 관련 문제가 나올 때 A* 알고리즘을 찾아보는 경우를 몇 번 본적이 있습니다. 그런데 A* 알고리즘은 대표적으로 네비게이션에서의 길찾기처럼 100% 정확한 최단거리를 내지 않아도 되고, 또 정점의 개수가 너무 많아 현실적으로 다익스트라 알고리즘을 사용하기 힘들 경우에 유용하게 사용할 수 있는 근사 알고리즘입니다. 그러나 저희가 문제를 푸는 상황에서는 대부분의 경우 정확한 답을 필요로 하지 근사치를 원하는게 아닙니다. 그래서 A* 알고리즘을 알 필요가 없고 그냥 다익스트라 알고리즘만 익히면 됩니다.

 

바로 다익스트라 알고리즘의 과정을 살펴보겠습니다. 설명을 돕기 위해 테이블은 ∞으로 초기화했습니다. 단 자기 자신과의 거리는 0일테니 1번 인덱스의 값은 0으로 둡니다.

 

다익스트라 알고리즘은 매 단계마다 도달할 수 있는 정점 중에서 시작점으로부터의 거리가 가장 가까운 정점을 구해서 그 거리를 확정하는 방식으로 동작합니다. 말 뜻이 잘 이해가 안 갈수도 있는데, 과정을 한 번 보고 나면 쉽게 이해가 가능합니다.

 

일단 1번 정점의 거리는 확정이 된거고 2, 3, 4, 5, 6번 정점이 모두 남아있습니다. 현재 1번 정점에서는 2, 3, 4번 정점으로만 갈 수 있는데 각 정점까지의 최단 거리는 각각 3, 2, 5입니다.

 

그러면 2, 3, 4번 정점 중에서 가장 가까운건 3번 정점이기 때문에 3번 정점까지의 거리를 2로 확정합니다. 주황색 테두리는 거리가 확정된 정점을 의미합니다.

 

다음으로 거리가 확정된 1, 3번 정점에서 갈 수 있는 정점이 뭐가 있냐 보면 2, 4번 정점이 있습니다. 2번 정점까지의 거리는 3이고 4번 정점까지의 거리는 1에서 3으로 갔다가 3에서 4로 가는 경로를 탔을 때 4가 됩니다.

 

둘 중에서 더 가까운건 2번 정점이어서 2번 정점까지의 거리를 3으로 확정합니다.

 

1, 2, 3번 정점에서 갈 수 있는 정점은 4, 5번 정점입니다.

 

둘 중에서 더 가까운건 4번 정점이어서 4번 정점까지의 거리를 4로 확정합니다.

 

다음으로 1, 2, 3, 4번 정점에서 갈 수 있는 정점은 5번 정점밖에 없습니다. 그러면 5번 정점의 거리는 10으로 바로 확정 가능합니다.

 

마지막으로 1, 2, 3, 4, 5번 정점에서 갈 수 있는 정점은 6번 정점밖에 없습니다. 그러면 6번 정점의 거리는 11로 바로 확정 가능합니다.

 

이렇게 1번 정점에서 출발해 다른 정점들로의 최단 거리를 구했습니다. 그런데 사실 설명의 편의를 위해서 구현의 디테일 하나를 생략한게 있습니다. 예를 들어서 현재 1, 2, 3번 정점의 거리를 확정했고 다음으로 추가할 정점을 찾는 상황을 떠올려볼겠습니다.

 

그러니까 지금 이 상황을 의미합니다. 이 때 4번 정점까지의 거리가 4이고 5번 정점까지의 거리가 11이란걸 알아낼 때 1번 정점과 연결된 정점의 목록을 다 살피고, 2번 정점과 연결된 정점의 목록을 다 살피고, 3번 정점과 연결된 목록을 다 살피면 구할 수 있습니다. 그런데 이렇게 구현을 하면 대략적으로 매 단계마다 간선을 다 훑어야 한다는 의미입니다. 그래서 O(VE)가 돼요. 반면 새 정점을 추가할 때 마다 미리 테이블에 거리를 계산해두고 거기서 최솟값을 찾는 방식으로 하면 O(V² + E)이고 일반적으로 E가 V보다 크니 O(VE)보다 O(V²+E)가 효율적입니다. 미리 테이블에 거리를 계산해둔다는게 무슨 의미인지 다시 한 번 과정을 보면서 이해해보겠습니다.

 

일단 여기까지는 똑같습니다.

 

여기서 차이가 생기는데 이 다음에 거리를 계산할 때 최단 거리 테이블에 3, 2, 5를 일단 써놓습니다. 물론 이 값이 확정은 아니고 나중에 바뀔 수 있습니다. 그리고 여기서 가장 가까운 정점을 찾아서 값을 확정하고 싶은데 테이블을 d라고 하면 d[2]부터 d[6] 중에서 최솟값을 찾으면 구할 수 있습니다. d[3]이 2로 최소이기 때문에 3번 정점의 거리를 확정할 수 있습니다.

 

그리고 이렇게 3번 정점의 거리를 확정한 다음에는 최단 거리 테이블을 갱신하는데 1번 정점에서 뻗어나가는 간선은 이미 다 확인을 했기 때문에 3번 정점에서 뻗어나가는 간선만 봅니다. 3번 정점에서 4번 정점으로 가는 간선이 있는데 이 간선을 이용해서 4번 정점까지 가는 거리는 d[3] + 2 = 4입니다. 그리고 이 4는 원래 테이블에 적혀있던 d[4] = 5보다 작기 때문에 d[4]를 4로 바꿉니다.

 

또 다시 가장 가까운 정점을 찾기 위해 d[2], d[4], d[5], d[6]을 확인하니 d[2]가 가장 작아요. 그렇기 때문에 2번 정점의 거리를 확정합니다.

 

그리고 2번 정점에서 뻗어나가는 간선을 가지고 최단 거리 테이블을 갱신합니다. 2번 정점에서 뻗어나가는 곳은 3번 정점과 5번 정점이 있는데 3번 정점은 이미 확정된 곳이니 냅두고, 5번 정점은 현재 테이블에 적혀 있는 d[5] = ∞보다 2번 정점을 타고 가는 d[2] + 8 = 11이 더 작기 때문에 11로 값을 갱신합니다. 만약 d[5]에 11보다 작은 값이 적혀있었다면 갱신을 하면 안됩니다. 이 다음부터는 설명이 없어도 충분히 이해하실 수 있을 것 같아서 상황만 그림으로 보여드리겠습니다.

 

 

이렇게 과정이 끝났습니다. 제가 볼 때 이거는 충분히 구현을 할 수 있습니다. 강의를 잘 따라오셨다면 이 정도는 짜실 수 있어야 합니다. 다음 슬라이드에 코드를 두긴 했는데 직접 시도해보도록 합시다. 최단 거리 테이블과 거리가 확정되었는지 여부를 관리할 배열을 두고 구현을 하면 됩니다.

 

구현은 그냥 하면 됩니다. fix는 고정됐는지 체크하는 배열이고 d는 거리 배열이에요. 함수 이름을 왜 dijkstra_naive라고 했냐면, 지금 이 코드는 O(V² + E)에 동작하는데 시간복잡도를 더 개선할 수 있습니다. 다익스트라 알고리즘은 다익스트라님이 1950년대 중반에 만든 알고리즘인데, 첫 발표때는 지금처럼 O(V² + E)에 동작하는 알고리즘이었습니다. 하지만 요즘과 같이 느림의 미학이 사라지고 속도만을 추구하는 21세기 감성에서는 O(V² + E)가 느린 감이 없잖아 있습니다. 더 빨리 동작하게 만들 수 있고 또 악랄한 출제자들은 보통 다익스트라로 푸는 문제를 낼거면 정점 개수 2만개 이렇게 둬서 O(V² + E)로는 절대 통과될 수 없게 만들어버립니다. 그래서 지금 이 구현은 그냥 동작 원리를 이해하는 차원에서 같이 짜본거지 앞으로 다익스트라를 이렇게 짤 일은 없고, 또 이렇게 짜면 느려서 써먹을 수가 없습니다.

 

개선된 구현 방법을 알아보기 전에 다익스트라 알고리즘이 왜 최단 거리를 구해주는지 간단하게 짚고 넘어가겠습니다. 알고리즘의 동작 방식을 보면 매번 아직 거리가 확정되지 않은 정점들 중에서 가장 가까운 정점을 찾아 거리를 확정합니다. 그러니까 쉽게 말해서 이것도 일종의 그리디인거고, 매번 확정된 정점까지의 최단 거리가 진짜 우리가 구한 값이란걸 보일 수만 있다면 납득을 할 수 있습니다. 이것도 수학적으로 엄밀하게 증명이 되긴 하는데 그냥 대략적인 느낌만 같이 가져가겠습니다.

 

딱 이 상황을 같이 보겠습니다. 1번 정점에서 2, 3, 4번 정점으로 뻗어나갔다가 그 중에서 가장 가까운 3번 정점의 거리를 확정지었습니다. 왜 이 상황에서 3번 정점까지의 거리가 2라고 확신할 수 있을까요? 귀류법으로 생각해서 중간에 다른 정점을 거치면 거리 2보다 더 짧은 경로로 갈 수 있다고 가정해보겠습니다.

 

근데 이건 애초에 말이 될 수가 없습니다. 예를 들어서 2번 정점을 거쳐서 가는게 1번 정점에서 바로 가는 것 보다 더 짧은 경로라고 해보겠습니다. 그런데 그러면 음수 간선이 없는 이상에야 애초에 1번 정점에서 가장 가까운 정점을 택할 때 2번 정점이 선택되었겠지 2번 정점 대신 3번 정점이 선택되었을리가 없습니다. 이런 논리로 생각하면 적어도 현재 갈 수 있는 정점 중에서 가장 가까운 정점까지의 거리는 확정할 수 있다는걸 알 수 있습니다.

 

그리고 앞의 논리를 계속 잘 발전시켜보면 왜 다익스트라 알고리즘이 음수 간선을 처리할수 없는지도 대답이 가능합니다. 지금 제시한 이런 그래프를 생각해보고 여기서 다익스트라를 돌려보겠습니다. 시작점은 1번 정점입니다.

 

제일 가까운게 3번 정점이니까 3번 정점까지의 거리를 2로 확정했습니다. 그리고 2번 정점까지의 거리는 3으로 기록이 됩니다.

 

그리고 다음으로 남아있는 2번 정점의 거리를 채우고 알고리즘은 끝납니다. 그런데 사실 3번 정점까지의 최단 거리는 2가 아니라 1번 정점에서 2번 정점으로 갔다가 3번 정점으로 가는 경로로 얻을 수 있는 -2입니다. 우리는 1번 정점에서 3번 정점이 제일 가깝기 때문에 3번 정점까지의 거리를 2로 확정한거였는데 사실은 2번 정점을 거쳐 가는게 더 이득인 상황이었습니다. 이처럼 음수 간선이 있으면 현재 갈 수 있는 정점 중에서 가장 가까운 정점까지의 거리를 확정할 수가 없어서 다익스트라 알고리즘의 논리가 성립될 수 없습니다.

 

그러면 다익스트라의 정당성도 대략적으로 봤고 음수 간선 얘기도 드렸으니 효율적인 구현을 같이 볼 수 있는데, 효율적인 구현은 다익스트라 알고리즘의 원리를 이해한 것과 별개로 꽤 어려울 수 있습니다. 일단 잠깐 복습 차원으로, 다익스트라 알고리즘에서 매번 가장 가까운 정점을 뽑아내야 합니다. 원소의 추가가 가능하고 최솟값의 확인/삭제가 효율적인 자료구조가 뭐였을까요? 이 질문을 보자마자 이거 바로 힙이에요 아니면 우선순위 큐에요 하고 답을 떠올릴 수 있어야 하는데 그렇게 됐나요 여러분? 저는 여러분들을 믿습니다.

 

우선순위 큐 단원에서도 이 자료구조가 다익스트라 알고리즘에서 쓰인다라고 말씀을 드렸었고 또 최소 신장 트리 단원에서 공부한 프림 알고리즘과 코드의 흐름이 많이 비슷합니다. 그렇긴 하지만 제 생각에 특히 우선순위 큐를 이용한 다익스트라의 구현은 혼자서 떠올려서 작성하기는 좀 힘든 것 같아서 뭐 도전을 해보시겠다면야 두 팔 벌려 환영하지만 일단 제 설명을 한 번 듣고 구현을 들어가시는게 어떨까 싶습니다.

 

과정은 이렇게 생겨있고 대략적으로 설명을 하면 우선순위 큐에 거리를 다 넣어둔다음 매번 최소인걸 선택하는 로직인데 어차피 글로 된 과정만을 보면 이해가 조금 쉽지 않을거라 바로 스텝 바이 스텝으로 살펴보겠습니다.

 

최단 거리 테이블은 0과 ∞으로 채워뒀고 또 앞에 있는 과정에서 언급한 것 처럼 (0, 시작점)을 우선순위 큐에 넣어야 합니다. 실제 구현을 할 때에는 STL priority_queue, pair를 이용하면 됩니다. 서술의 편의를 위해 우선순위 큐의 원래 구조를 무시하고 그냥 배열처럼 나타내겠습니다. 초기 세팅은 완료됐고 과정을 시작하겠습니다. 시작점은 1번 정점입니다. 그리고 이전과 달리 거리가 확정되었는지를 별도로 관리할 필요가 없습니다.

 

먼저 우선순위 큐에서 가장 거리가 작은 원소를 선택합니다. 지금 우선순위 큐에서는 (0, 1)이 선택됩니다. 실제 구현을 할 때에는 선택한 후에 별도의 변수에 두고 바로 제거를 하겠지만 보기 편하라고 이 슬라이드 안에서는 그대로 두겠습니다.

 

편의상 최단 거리 테이블을 d 테이블이라고 부르면, 우선 d[1] = 0이 맞는지 확인합니다. 만약 일치하지 않는다면 해당 원소를 제거하고 넘어가지만 지금은 일치하기 때문에 과정을 이어나갑니다. 1번 정점에서 갈 수 있는 정점은 2, 3, 4번 정점이 있고 거리는 3, 2, 5인데 원래 최단 거리 테이블에 있던 ∞보다 3, 2, 5가 더 작으니까 최단 거리 테이블을 셋 다 갱신해줍니다. 그리고 힙에 (거리, 정점) 쌍을 뜻하는 (3, 2), (2, 3), (5, 4)를 추가합니다.

 

우선순위 큐가 비어있지 않기 때문에 우선순위 큐에서 가장 거리가 작은 원소를 선택합니다. 지금은 (2, 3)이 선택됩니다. 우선 d[3] = 2인지 확인하고, 맞기 때문에 과정을 이어갑니다.

 

3번 정점에서 갈 수 있는 정점은 4번 정점이 있습니다. 3번 정점을 거쳐서 4번 정점으로 갈 때의 최단 거리는 3번 정점까지의 거리와 간선의 가중치를 합쳐 d[3] + 2 = 4입니다. 이 값이 d 테이블에 저장된 값보다 작을 경우 최단 거리 테이블에 쓰고 우선순위 큐에 삽입을 할건데 기존에는 5가 저장되어 있었으므로 4로 갱신을 하고 힙에 (4, 4)를 삽입합니다. 이렇게 되면 지금 우선순위 큐에 4번 정점에 대한 원소가 2개 있는걸 확인할 수 있습니다. 과연 이게 맞나 싶을 수 있는데 맞게 가고 있는거니까 걱정할 필요가 없습니다.

 

우선순위 큐가 비어있지 않기 때문에 우선순위 큐에서 가장 거리가 작은 원소를 선택합니다. 지금은 (3, 2)가 선택됩니다. 우선 d[2] = 3인지 확인하고, 맞기 때문에 과정을 이어갑니다.

 

2번 정점에서 갈 수 있는 정점은 3, 5번 정점이 있습니다. 2번 정점을 거쳐서 각각으로 가는 거리는 d[2] + 2 = 5, d[2] + 8 = 11입니다. 사실 다익스트라 알고리즘의 원리 상으로 3번 정점까지의 거리는 이미 2로 확정이 됐습니다. 그렇긴 하지만 앞에서 말했듯 지금 이 우선순위 큐를 이용한 구현에서는 특정 정점의 거리가 확정됐는지 여부를 따로 저장하지 않기 때문에 3번 정점 또한 d[2] + 2 = 5로 2번 정점을 가쳐서 갈 때의 거리를 계산해야 하고 그 값을 d[3]과 비교해야 합니다. 하지만 당연히 기존의 값 d[3] = 2가 2번 정점을 거쳐갈 때의 거리 d[2] + 2 = 5보다 작기 때문에 아무 일도 일어나지 않습니다. 5번 정점의 경우에는 기존의 값이 ∞이었으니까 11로 갱신을 해주면서 우선순위 큐에도 (11, 5)를 삽입합니다.

 

우선순위 큐가 비어있지 않기 때문에 우선순위 큐에서 가장 거리가 작은 원소를 선택합니다. 지금은 (4, 4)가 선택됩니다. 우선 d[4] = 4인지 확인하고, 맞기 때문에 과정을 이어갑니다.

 

4번 정점에서 갈 수 있는 정점은 5번 정점이 있습니다. 4번 정점을 거쳐서 5번 정점으로 가는 거리는 d[4] + 6 = 10이죠. 이 값이 d 테이블에 저장된 값보다 작을 경우 최단 거리 테이블에 쓰고 우선순위 큐에 삽입을 할건데 기존에는 11이 저장되어 있었으므로 10으로 갱신을 하고 힙에 (10, 5)를 삽입합니다.

 

여기서 이전엔 없던 좀 재밌는 현상이 발생하는데, 우선순위 큐에서 가장 작은 원소인 (5, 4)가 선택됐습니다. 그런데 d[4] = 5가 맞는지 확인해보면 d[4] = 4여서 이 원소는 잘못된 원소입니다. 이 5라는 값이 어디서 왔나 보면 1에서 바로 4로 가는 경로를 추가할 때 생겨난 값이지만 1->3->4로 가는 더 짧은 경로가 나와서 쓸모가 없어진 원소입니다. 그렇기 때문에 아무 처리도 하지 않고 그냥 건너뜁니다.

 

다음으로 (10, 5)가 선택될거고 d[5] = 10인지 확인하면 맞습니다. 일치하기 때문에 과정을 이어갑니다.

 

이건 설명이 없어도 알 수 있겠죠? d[6]을 갱신하고 우선순위 큐에 (11, 6)을 추가합니다.

 

이번에는 거리가 같아서 (11, 5) 혹은 (11, 6) 둘 중에 아무거나 선택해도 되지만 그냥 (11, 5)가 선택됐다고 해보겠습니다. d[5] = 11이 아니라 d[5] = 10이어서 이 원소는 잘못된 원소이고 건너뜁니다.

 

마지막으로 (11, 6)을 선택하고 d[6] = 11이기 때문에 과정을 이어갑니다.

 

6번 정점에서 갈 수 없는 정점이 없기 때문에 탐색할 곳이 없고, 이제 우선순위 큐가 비었기 때문에 과정이 끝납니다. 이렇게 과정을 살펴봤고 시간복잡도가 조금 헷갈릴 수 있는데, 그냥 우선순위 큐에 추가될 수 있는 원소의 수를 생각해보면 간선 1개당 최대 1개의 원소가 추가될 수 있기 때문에 시간복잡도는 O(ElgE)입니다. 다른 곳에서 다익스트라 알고리즘의 시간복잡도를 찾아보면 O(ElgV)라고 되어 있는 곳도 여럿 있을텐데 O(ElgE)나 O(ElgV)나 big-O의 관점에서 동일합니다.

 

이전에 짰던 O(V²+E)와 비교해보면, 만약 E가 V²에 가깝다면 사실 우선순위 큐를 쓰지 않는 구현이 더 낫지만 보통 다익스트라로 풀리게끔 유도하는 문제에서는 V를 많이 크게 두고 E는 V²까지 안가게 적당히 작게 하는 경우가 많아서 그냥 앞으로 다익스트라 알고리즘은 우선순위 큐를 이용해서 짠다고 생각을 하시면 됩니다.

 

그러면 진짜 구현을 해볼 시간입니다. 직접 해보셔도 되고 난이도가 꽤 있기 때문에 그냥 코드를 바로 보셔도 됩니다. 직접 짜보실거면 BOJ 1753번: 최단경로 문제에 제출을 해서 검증할 수 있습니다. 일단 제 코드를 바로 보여드리겠습니다.

 

공간이 좁아서 일부 주석을 뺐고 주석이 포함된 코드는 링크에서 확인 가능합니다. pair의 비교 함수를 별도로 선언하기 싫어서 간선이나 우선순위 큐의 원소를 (거리, 정점 번호) 순서로 배치했습니다. 그리고 우선순위 큐는 28-30번째 줄처럼 선언해서 min heap으로 뒀습니다. 결국 34-42번째 줄의 로직이 핵심인데 앞에서 같이 본 흐름 그대로이긴 합니다. 한번 찬찬히 잘 살펴보도록 합시다. (코드)

 

한편으로 cur.X, cur.Y, nxt.X, nxt.Y 값이 뭘 의미하는지 조금 헷갈릴 수 있고 또 구현을 하다가 실수할 수도 있습니다. 그래서 예를 들어 cur_idx = cur.Y, cur_dist = cur.X 이런 식으로 별도의 변수를 두고 코드를 작성해도 상관없습니다. 그건 각자의 편의에 따라 알아서 하시면 됩니다.

 

그리고 정말 주의하셔야 하는게 잘못 구현한 다익스트라 코드가 인터넷에 진짜 많이 돌아다닙니다. 예를 들어 우선순위 큐에 (정점 번호, 거리) 순으로 넣어서 거리가 작은 원소를 꺼내는게 아니라 정점 번호가 작은 순으로 끄집어낸다거나, 우선순위 큐를 max heap으로 둔다거나, 36번째 줄처럼 거리가 다르면 그 원소를 버리는 처리를 하지 않는다거나 하는 식의 실수를 할 수가 있습니다. 그리고 더 문제가 뭐냐면, 저런 실수를 해도 보통 답은 잘 나오는데 시간복잡도가 이상해지는 경우가 많습니다. 그러면 예제로 주어지는 작은 케이스에서는 문제를 못찾다가 정작 제출을 하면 계속 틀리게 됩니다. 그래서 익숙해질 때 까지는 한동안 제 구현체를 참고해서 이 흐름을 잘 기억해둘 필요가 있습니다. 나중에 직접 짜본 후에도 제 코드랑 비교하면서 제대로 짠게 맞는지 꼭 검증해보시길 바랍니다.

 

한편으로 문제의 조건에서 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다고 했는데도 그에 대한 처리가 없는 것을 볼 수 있는데, 별도로 처리를 하지 않아도 어차피 다익스트라 알고리즘 과정을 진행하다보면 비용이 더 큰 간선은 알아서 반영이 되지 않기 때문입니다.

 

다음으로 경로 복원 방법을 알아보겠습니다. 현재 저희는 최단 거리만 알고 있지 실제로 어떤 경로로 가야 하는지는 모릅니다. 그리고 플로이드 알고리즘처럼 다익스트라 알고리즘에서도 경로 복원이 가능합니다. 플로이드 알고리즘에서 이미 한 번 살펴봤기 때문에 충분히 혼자 힘으로 떠올릴만 합니다. 고민을 해봅시다.

 

방법은 플로이드 알고리즘에서 한 것과 크게 다르지 않아요. 최단 거리 테이블이 갱신될 때 어디를 거쳐가면 되는지를 남기면 됩니다. 이 테이블은 시작점에서 나에게로 올 때 직전에 어디를 방문했는지 기록하는 테이블이어서 pre 테이블이라고 쓰겠습니다. pre 테이블을 언제 어떻게 갱신하면 되는지 같이 알아보겠습니다.

 

다익스트라의 구현 방법을 설명할 때 보여드린걸 다시 가져왔는데, 이렇게 최단 거리 테이블의 값을 갱신할 때 pre 테이블도 같이 바꾼다는 뜻입니다. d[2], d[3], d[4]의 갱신이 일어나니 pre[2], pre[3], pre[4]에는 1을 기록하면 됩니다.

 

그 다음은 3번 정점으로 인해 4번 정점까지의 거리가 갱신되는 상황인데 이 때에는 pre[4] = 3으로 바꾸면 됩니다.

 

그 다음은 2번 정점으로 인한 갱신이 발생하는 상황입니다. pre[5]는 2로 바뀌지만 3번 정점의 거리는 바뀌지 않으니 pre[3]은 바꾸면 안됩니다. 이 뒤는 설명 없이 바로 보여드리겠습니다.

 

이렇게 과정이 끝났고, pre 테이블을 다 채운 후 이 정보를 바탕으로 경로를 복원하는건 그냥 pre를 타고 시작점을 만날 수 계속 이동하는 방식으로 처리가 가능합니다. 이건 바로 앞에서 배운 플로이드 알고리즘 단원에서 언급이 있어서 바로 코드를 살펴보겠습니다. BOJ 11779번: 최소비용 구하기 2 이 문제를 가지고 확인을 해볼 수 있습니다. 앞의 다익스트라 코드에서 조금만 바꾸면 되니까 직접 시도해보도록 합시다.

 

코드가 길어서 일단 출력 전까지만 같이 보겠습니다. 코드가 대부분 유사하니 pre 배열와 관련한 부분만 보면 36번째 줄과 같이 최단 거리의 갱신이 일어날 때 38번째 줄과 같이 pre 값을 바꿔줍니다.

 

이후에는 d[en] 값을 출력하고 경로 복원을 하면 끝입니다. 이 문제를 통해서 배울 수 있는 또 한가지 정보가 있는데 하나의 시작점에서 다른 모든 정점까지의 거리나 경로를 구하는 것이 아니라 하나의 시작점에서 하나의 끝점까지의 거리나 경로를 구하는 상황이라고 하더라도 다익스트라 알고리즘을 쓰면 된다는걸 배울 수 있습니다. (코드)

 

다익스트라 알고리즘은 되게 유명하면서도 개념과 구현이 적당히 어려워서 면접이나 코딩테스트에서 물어보기 좋은 알고리즘입니다. 특히 우선순위 큐를 이용한 구현을 할 때 실수하지 않도록 정말 주의를 하시고 공개된 자료를 참조할 수 있는 상황이면 사실 그냥 매번 새로 짜지 말고 제 구현체를 가져와서 쓰는 것도 나쁘지 않습니다. 그리고 플로이드처럼 응용 문제에는 다익스트라 알고리즘의 원리 자체를 제대로 이해하고 있어야 해결할 수 있는 문제를 몇 개 뒀으니까 큰 뜻이 있다면 응용 문제까지 한 번 풀어보도록 합시다.