[ 개념 ] 37. 다익스트라(Dijkstra) 알고리즘

> 다익스트라 알고리즘

---

이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요.

그래프... 정말 어렵고, 답없고, 온갖 문제가 많기로 유명합니다.

그 중에서도 처음을 장식할 최단 경로 알고리즘은 그 종류부터 3개나 됩니다.

그 중 첫 번째 알고리즘인 다익스트라 알고리즘(Dijkstra's algorithm)에 대해서 알아보겠습니다.

이 알고리즘이 하는 일은 그래프의 어떤 정점 하나를 시작점으로 선택하고,

나머지 정점들로의 최단거리를 모두 구합니다. 시작점 자신이야 뭐 그냥 0입니다.

정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도를 갖습니다.

그래프는 무향이거나 유향인데 대체로 유향인 경우가 많고, 간선마다 이동거리가 존재합니다.

또한 모든 거리값이 음수가 아닐 때만 사용할 수 있습니다.

이 이동거리가 거리 대신 비용(cost)이라는 용어로 대체되고서 최소비용을 구하라고 할 수도 있는데 같은 표현입니다.

이런 무향 그래프를 예로 들어 설명하겠습니다. 영문 위키 예제를 퍼온 겁니다.

0번 정점을 시작점으로 하여, 0번에서 다른 정점으로 가는 최단 경로를 다 구할 겁니다.

다익스트라 알고리즘은 이렇게 작동합니다.

① 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.

② 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

맨 처음에는 시작점으로의 거리만 0이고 나머지는 다 거리가 무한입니다.

정점 i, j 사이의 거리를 d, 거리 테이블을 dist라고 부르겠습니다.

dist가 제일 작은 것이 시작점이므로(나머지는 다 무한), 시작점인 0번 정점을 방문하고 이런 일을 합니다.

0번에서 바로 갈 수 있는 인접한 정점은 1, 2, 5번 정점이고,

0번을 통해 k번 정점으로 가는 거리는 dist[0] + d[0][k]이고, 이게 만약 dist[k]보다 작다면 dist[k]가 갱신됩니다.

지금은 0번을 제외한 모든 정점으로의 dist 값이 무한대이므로 무조건 갱신됩니다.

그 다음, 아직 방문하지 않은 정점 중 dist가 제일 작은 곳이 1번이므로

1번 정점을 방문하여 인접한 2, 3번 정점의 거리 갱신을 시도합니다.

0번 정점 또한 인접하지만, 0번 정점은 이미 방문한 상태이므로 아무것도 하지 않습니다.

여기서 2번 정점의 경우는 거리가 갱신되지 않습니다. dist[2]가 이미 dist[1] + d[1][2]보다 작거나 같기 때문.

아... 여기부터는 아래의 간선에 실수로 방향을 안 없애놨네요. 무시해주시기 바랍니다.

여튼 이번엔 dist[2]가 제일 작으므로 2번 정점을 방문하여 3, 5번 정점으로의 거리를 갱신합니다.

그 다음은 5번 정점을 방문합니다.

3, 4번 정점이 남았는데 둘의 dist가 같네요. 이럴 때는 아무거나 방문해도 됩니다.

3번 정점에서 4번 정점의 거리 갱신을 시도했으나 먹히지 않았습니다.

마지막으로 4번 정점만 남았을 때는 나머지 정점을 다 방문한 상태이므로 아무것도 하지 않습니다.

여기까지가 다익스트라 알고리즘 작동의 과정인데, 이게 끝나고 나면 각 dist 값이 0번 정점으로부터의 실제 최단 거리가 됩니다.

즉 매 루프에서 방문된 상태의 정점의 dist값은 이미 최단거리고, 앞으로 절대 안 바뀐다는 겁니다.

왜일까요? 만약 이렇게 했는데 최단거리가 구해지지 않는 경우도 있을까요?

아직 방문하지 않은 정점들 중 가장 dist 값이 작은 정점이 u고, 사실 dist[u]는 최단거리보다는 아직 크다고 해 봅시다. 이때 u를 방문하면 dist[u] 값은 최단거리가 아니게 되겠죠.

또한 dist[u]가 아직 최단거리가 아니라는 말은, 다른 임의의 정점 v를 거치는 경로를 통해 최단거리로 갱신될 수 있다는 말입니다. 즉 dist[u] > dist[v] + d[v][u]인 어떤 정점 v가 존재할 겁니다.

그런데 아직 방문하지 않은 정점 중에서 dist 값이 제일 작은 게 u라고 했으니까 v는 방문한 상태일 겁니다.

그런데 v를 방문했을 때 dist[u]는 이미 dist[v] + d[v][u]로 갱신되고 말았을 겁니다.

따라서 저렇게 될 수 있는 경우는... 없습니다..

런데 위 증명에서 중요하게 작용하는 성질이 바로 d 값이 항상 0 이상이라는 사실입니다.

만약 d 값이 음수인 경우도 있다면 이 과정이 성립하지 않아서, 진짜로 최단 경로를 못 구할 수도 있습니다.

이때는 조금 더 느리지만 전용 알고리즘인 벨만 포드 알고리즘을 써야 하고 이건 다음 글에서 쓸게요.

그럼 이제 이걸 구현해야 합니다.

가장 문제인 부분은 아직 방문하지 않은 정점들 중에서 dist 값이 제일 작은 정점을 찾아 방문하는 부분.

이걸 그냥 dist 값들을 다 비교해서 찾다가는 매번 O(V)고, 루프는 V-1번 실행되니까 O(V^2)의 시간복잡도가 발생하고 말아서 너무 큽니다.

따라서 이걸 영리하게 찾아야 하는데요, 여기에 사용되는 게 바로 우선순위 큐입니다!

최소 힙을 하나 마련합니다. 그리고 정점 u를 방문해서 인접한 정점 v의 거리를 갱신할 때마다 최소 힙에 (dist[v], v) 쌍을 넣습니다.

pair는 첫 번째 인자의 대소 비교를 먼저 하므로, dist 값이 작으면 작을수록 우선순위 큐에서 먼저 나오겠죠.

dist 값이 제일 작은 걸 뽑아서, 그 두 번째 인자인 정점 번호를 사용하면 됩니다.

또한 v를 방문하기 전에 값이 여러 번 갱신될 수도 있고, 그럼 서로 다른 (d, v) 값들이 우선순위 큐 안에 존재할 수 있는데 이땐 쿨하게 그냥 제일 작은 d 값 하나만 뽑아서 쓰면 되고 우선순위 큐가 이걸 자동으로 해결해 줍니다.

다만 아직 우선순위 큐에 남아있는 v 정점에 관한 쌍은 어떻게 하느냐? 이건 그냥 놔뒀다가 추후 top에서 나타나면 무시합니다. 즉, 꺼낸 정점이 이미 방문한 곳이면 무시하고 다음 top을 꺼내면 됩니다.

이렇게 하면, 한 정점에 최대한 많은 갱신이 이루어진다고 해도 넉넉잡아 V^2번 갱신이 이루어져서 PQ에 한 순간에 V^2개의 정보가 들어있다고 해도

원래 연산에 O(logN)의 시간이 드는 우선순위 큐 입장에서는 O(log(V^2)) = O(2logV) = O(logV).

즉, 최대 O(E)번 우선순위 큐에서 top을 꺼내는 연산 O(logV),

루프 전체를 통틀어서 인접한 정점으로의 거리를 갱신하는 부분도 최대 O(E)번 이루어질 것이므로

총 시간복잡도 합은 O(ElogV)입니다.

아, 여기서 O(E)라는 시간복잡도 또한 그래프를 인접 리스트로 구현했을 때의 말입니다.

인접행렬로 구현했다면 매번 인접한 정점을 찾아야 하니 루프마다 O(V)의 시간이 소요되어서 총합 O(V^2)가 될 것입니다...

한 가지 예외처리를 해야 하는 경우가 있습니다.

그래프 자체가 연결 그래프가 아니거나, 아니면 유향 그래프에서 시작점에서 어떤 정점으로 못 갈 때는 루프를 꼭 V-1번 돌지 못합니다. 중간에 우선순위 큐가 텅텅 비어버리게 되고 이때는 그냥 나와야 합니다.

아직 방문하지 못한 정점들의 경우는 거리가 무한으로 남아 있고, 이는 시작점에서 그 정점으로 갈 수 없다는 뜻이겠지요.

다익스트라 관련 문제

1753번: 최단경로

위에서 설명한 문제입니다.

1916번: 최소비용 구하기

역시 기본적인 다익스트라 알고리즘 연습 문제이며,

시작점과 도착점이 정해지는 데다가 항상 이동 가능해서 오히려 더 쉬울지도?

간선이 최대 10만 개고 각 비용이 최대 10만이어서 10만*10만은 int 범위를 넘어가지만,

도시 개수가 최대 1,000인지라 가능한 최단거리는 100,000*999라서 int 범위 안에 있습니다.

1504번: 특정한 최단 경로

반드시 거쳐야 하는 정점이 a, b일 때 가능한 경로는 1->a->b->N, 1->b->a->N 두 가지이고 둘 중 더 작은 경로가 답입니다.

1->a->b->N으로 가는 최단 경로는 그냥 1->a, a->b, b->N 최단 경로 3개를 더하면 되고, 이 중 하나라도 경로가 없는 경우 전체 경로가 존재하지 않습니다.

따라서 1, a, b 세 개의 정점을 시작점으로 하여 각각 다익스트라 알고리즘을 돌려 다른 모든 정점으로의 거리 정보를 얻고, 이들을 조합해서 문제를 풀면 될 것입니다.

4485번: Obstacle Course

이번엔 간선이 아니라 각 칸에 비용이 있네요.

이때는 인접한 두 칸 u, v가 있을 때 u에서 v로 가는 비용을 cost[v]로 두면 됩니다.

그러면 어떤 방을 여러 번 방문하면 cost가 중첩되어서 쌓이는 게 아니겠느냐...? 사실 한 방을 두 번 이상 방문한 시점에서 그건 이미 최단경로가 아니라서 신경쓰실 필요 없습니다.

시작점 S의 dist 값이 0이 아니라 cost[S]인 상태로 시작하여 dist[E]를 구하거나, 아니면 마지막에 dist[E]에 cost[S]를 더해서 출력하면 됩니다.

1238번: 파티

1~N번을 각각 시작점으로 해서 다익스트라 알고리즘을 한 번씩 돌려야 합니다.

각각 X번 마을로의 최단경로를 구해야 하고, X번 마을에서는 나머지 다른 마을로의 모든 최단경로를 구해야 하죠.

이 모든 정보를 조합해서 가장 긴 왕복거리 값을 찾으면 됩니다.

X번이 아닌 다른 마을에서 다익스트라 알고리즘을 시도할 때는 X번 마을을 방문하면 바로 알고리즘을 종료해버리는 게 시간 절약에 도움이 됩니다.

이론상의 시간복잡도는 O(N^2logN + NM)이네요.

1261번: 알고스팟 (★)

Obstacle Course 문제와 똑같이 풀면 됩니다.

벽인 방으로 이동하려면 벽을 뚫어야 하고 이건 cost 1이 들어감을 의미하죠.

뚫어야 하는 최소 벽 개수가 즉 최소 비용이 되겠습니다.

10473번: 인간 대포 (★)

기하 문제인데요. 시작점, 목적지, 그 외 모든 대포를 정점으로 두고

각 정점 사이의 최단 이동 시간을 죄다 구하는 것을 시작으로 다익스트라 알고리즘을 사용합니다.

시작점에서는 도착점이나 다른 모든 대포로 그냥 걸어가는 직선 거리를 구해서 시간을 구하고,

각 대포에서는 다른 대포나 도착점으로 가는 최단시간을 구해야 하는데, 일단 대포로 갔다는 건 발사는 했다는 말이므로 착지한 후 그대로 걸어가야 하는데 경우에 따라 발사하면서 목적지를 지나쳐 갈 수도 있는 등 여러 가지 케이스를 다 처리해 주셔야 합니다.

2211번: 네트워크 복구 (★)

prev 배열의 저력을 보여줄 때입니다.

1번 정점이 슈퍼컴퓨터이고, 간선들 중 일부만 골라서 모든 정점을 잇게 하되, 최소 개수의 간선만 고르라고 하네요.

이때는 정점 개수가 N인 그래프가 연결 그래프일 때 반드시 N-1개의 간선만 골라서 정점이 N개인 트리를 만들어서 조건을 만족시킬 수 있습니다. 이걸 신장 트리(spanning tree)라고 하는데 바로 다음 글에서 자세히 다루도록 하죠.

그러나 다른 조건이 있는데, 복구한 간선들만을 통해 도달할 수 있는, 1번 정점으로부터 다른 정점까지의 최단 경로가 원래와 같아야 한다네요(줄어들 수는 없습니다).

이때는 놀랍게도, 1번을 시작점으로 하여 다익스트라 알고리즘을 돌린 후 1번 정점을 제외한 각 정점 u에 대해 prev[v] = u라고 할 때, 간선 (u, v)들만 모아서 복구하면 문제가 해결됩니다.

특정 정점에서 prev 배열만 역으로 계속 따라가다 보면 시작점에서 도착점으로 가는 최단 경로를 역순으로 얻을 수 있다는 점에서 착안한 것입니다.

16681번: 등산

각 마을마다, 1번 마을로부터의 거리와 N번 마을로부터의 거리를 구하면 됩니다. 1번과 N번을 각각 시작점으로 하여 다익스트라를 2번 돌리면 해결됩니다. 물론 높이가 높아지는 정점으로만 이동하게 해야겠죠.

5719번: 거의 최단 경로 (★)

어렵습니다. 한 번 최단 경로가 얼마인지 구한 후, 최단 경로로 가능한 모든 경로의 간선을 다 없애는 짓을 해야 합니다.

일단 시작점 S와 도착점 E가 있고 각 정점의 시작점으로부터의 거리 dist 값들이 있을 때, dist 값들을 다 구하고 나서 이런 행동을 해서 최단경로의 간선을 모두 체크할 수 있습니다.

① 큐에 시작점을 넣고 시작합니다.

② 큐의 맨 위에 있는 정점을 꺼내서 u라 하면, 인접한 정점 v 중 dist[u]+d[u][v] = dist[v]인 모든 v를 찾아 큐에 넣고, 그러한 v에 대해 간선 (u, v)를 가능한 최단 경로에 속한다고 판별합니다.

일종의 BFS 형태입니다. 이렇게 경로를 다 구하고 삭제하는 과정을 거친 후 한 번 더 다익스트라 알고리즘을 돌려야 하네요.

처음부터 S에서 E로 갈 수 없거나, 간선 삭제 후 갈 수 없게 되거나 하는 경우를 잘 처리해 주셔야 합니다.

15422번: Bumped!

BFS 글에서 응용 문제들을 유심히 보셨다면, 비슷하게 응용해서 이런 문제도 풀 수 있습니다.

이 문제의 경우 그래프가 주어짐과 동시에, 최대 하나만 골라서 공짜로 이용할 수 있는 비행권들이 있습니다.

벽 부수고 이동하기 문제와 비슷하게, 제공된 비행권들 중 하나를 사용했느냐 아니냐로 각 정점을 이등분해서 거기에 대해 다익스트라 알고리즘을 돌리면 풀 수 있습니다. 비행권은 양방향 간선이 아님에 주의하세요.

1162번: 도로포장 (★)

K가 최대 20밖에 안 돼서 이런 걸 시도할 수 있습니다.

정점 번호와 앞으로 더 포장할 수 있는 도로 개수를 갖고 있는 새로운 형태의 정점 (u, k)들을 생각해 봅시다. 그렇다면 시작점은 (1, K)이며 답은 (N, 0) ~ (N, K) 중 최솟값일 겁니다.

그냥 있던 도로를 따라간다면 (u, k)에서 (v, k)로 이동하게 되고 이때의 거리는 그냥 d[u][v]입니다.

그러나 k > 0일 때는 도로 하나를 포장할 수 있고, (u, k)에서 (v, k-1)로 cost 0을 들여서 이동할 수 있습니다.

이런 식으로 그래프를 모델링해서 다익스트라 알고리즘을 적용하면 됩니다.

10217번: KCM Travel (★)

도로포장 문제와 상당히 유사합니다.

이번엔 금액이라는 또다른 제한이 주어지는데, 공항 수 N이 최대 100이고 금액도 최대 10,000이라서

각 정점에다 현재 가지고 있는 돈의 정보를 묶어 (n, m) 형태의 정점을 새로 모델링할 수 있고, 시작점 (1, M)에서 도착점 (N, ?)으로 가는 최단시간이 되겠네요. 도착점에서 가지고 있을 돈의 액수는 아무래도 좋고 일단 도착만 가능하면 됩니다.

물론, 이번에도 돈이 부족하면 해당 간선은 못 지나갑니다. (u, v) 방향 간선이(u->v) 시간 d, 비용 c가 든다면 (u, 15)에서는 (v, 15-c) 정점으로 시간 d를 들여서 갈 수 있는 것이고, 비용 c만큼도 부족하다면 아예 갈 수 없습니다.

총 정점 개수가 O(NM)으로 약 백만 개지만 시간제한도 10초나 되어서 다익스트라 알고리즘으로 무리없이 풀 수 있습니다.

그리고 이 문제의 경우 항상 어떤 간선을 지날 때마다 최소 1의 비용이 소모되어서 DP로도 푸는 게 가능합니다.

 

출처 : blog.naver.com/kks227/220796963742