ho94949's profile image

ho94949

January 10, 2019 15:00

그래프 모델링 - 최단경로

서론

실생활의 다양한 문제들은 (유향)그래프로 표현이 가능합니다. 이 포스트에서는 문제들을 그래프로 변형하는 방법과, 그래프로 변형하여 문제를 간단하게 푸는 방법에 대해 소개합니다.

그래프

“내가 가고 싶은 도시들이 있고, 그 도시들 사이에 교통 수단을 표현하려면 어떤 방법을 써야할까요?”

그래프(graph)는 정점(vertex, 주로 $V$ 로 표기)와 간선(edge, 주로 $E$ 로 표기)로 이루어진 구조입니다. 각 정점은 임의의 집합입니다. 즉, 아무것이나 될 수 있습니다. 각 간선은 정점 두개를 잇는 선입니다. 이 때, 각 정점의 순서가(즉, 방향이) 있으면 유향그래프, 없으면 무향그래프라고 말합니다. 이 게시글에서는 유향그래프를 주로 다룰 것 입니다. 정점은 주로 점으로, 간선은 주로 선으로 표현합니다. 아래의 그래프는 정점은 {개성, 서울, 인천, 세종, 대전, 광주, 대구, 울산, 부산} 이고, 간선은 {서울->인천, 서울->부산, 서울->대전, 인천->서울, 세종->서울, 세종->광주, 대전->세종, 대전->대구, 광주->세종, 대구->울산, 대구->부산, 울산->대구, 부산->대구, }이 있습니다. 여기서 정점은 각 도시, 간선은 각 교통수단이 됩니다.

방향과 길이가 있는 그래프의 예

우리는 이 그래프의 간선에 좀 더 정보들을 줄 수 있습니다. 예를 들면, 각 도시에서 도시로 가는데 드는 비용 같은 정보들을 줄 수 있습니다. 예를 들면, 서울->인천(2,000), 대전->세종(5,000) 처럼, 간선에 추가적인 정보를 줄 수 있습니다. 이 비용을 간선의 가중치(weight) 라고 합니다. 아래 설명에서는 가격을 토대로 한다면 {서울->인천(2,000), 서울->부산(80,000), 서울->대전(20,000), 인천->서울(3,000), 세종->서울(10,000), 세종->광주(20,000), 대전->세종(5,000), 대전->대구(15,000), 광주->세종(25,000), 대구->울산(10,000), 대구->부산(23,000), 울산->대구(10,000), 부산->대구(20,000)}을 사용합니다. 만약에 가중치가 가격이 아니라 교통수단을 사용한 횟수 라고 한다면, 간선의 가중치는 모두 1일 것입니다.

그래프는 현실의 많은 정보들을 좀 더 추상적으로 다루는데 도움을 줍니다.

그래프에서의 최단경로

“서울에서 울산까지 가는 가장 저렴한 방법은 무엇인가요?”

이제 그래프에서의 최단경로 문제입니다. 우리는 환승(경로)를 포함해서 서울(출발 정점)에서 울산(끝 정점) 까지 가는데 가격(가중치의 합)이 제일 작은 방법이 궁금합니다. 일단 경로에 대해서 설명을 하겠습니다.

경로란, 간선들을 순서를 가지고 나열해 놓은 것입니다. 여기서 규칙은, 간선들을 나열 할 때 간선의 끝이 다음 간선의 시작이 되어야 한다는 것 입니다. 예를들어 (서울->부산, 부산->대구, 대구->울산)은 간선들을 나열해 놓은 것이고, 한 간선의 끝은 다음 간선의 시작이 됩니다. 여기서 처음 간선의 시작을 경로의 시작 정점이라고 하고, 마지막 간선의 끝을 경로의 끝 정점이라고 합니다. 위 경로는 서울에서 시작하여 울산으로 가는 경로를 나타냅니다. 서울에서 울산으로 가는 경로는 하나가 아닐 수도 있습니다. 예를 들면, (서울->대전, 대전->대구, 대구->울산)도 서울에서 울산으로 가는 경로입니다.

여기서 경로들에 가중치를 붙여서 표현해 봅시다. 가중치를 가격이라고 한다면 (서울->부산(80,000), 부산->대구(20,000), 대구->울산(10,000)), (서울->대전(20,000), 대전->대구(15,000), 대구->울산(10,000)) 이 될 것입니다. 이 가중치의 합을 경로의 가중치(weight of path)라고 합니다. 여기서 가중치가 가격이기 때문에, 경로의 가중치는 시작에서 끝까지 가는데 드는 가격을 의미할 것입니다. 첫 경로의 가중치는 110,000, 둘째 경로의 가중치는 45,000입니다.

최단경로(shortest path)라는 것은 가능한 경로 중 가중치가 제일 적은 경로를 의미합니다. 서울에서 울산으로 가는 경로중에 제일 가중치가 작은 경로는 45,000인 즉, 45,000원을 쓰는 두번째 경로일 것입니다. 이 최단경로는 굉장히 유용합니다. 여기서는 서울에서 울산으로 가는 가장 싼 방법을 구했습니다.

다익스트라의 알고리즘

다익스트라의 알고리즘(Dijkstra’s Algorithm)은 특정한 시작점에서 다른 모든 정점까지의 최단경로의 가중치를 구하는 알고리즘입니다. 이 알고리즘은 가중치가 0 이상의 수인 경우에 잘 동작하고, 좋은 자료구조를 사용한 경우에 $ O(E + V log V) $ 의 시간이 듭니다. 알고리즘은 다음과 같이 동작합니다.

  1. 시작점의 최단경로의 가중치를 0으로 두고, 다른 모든 점의 최단경로의 가중치를 무한이라고 설정합니다. 모든 점의 최단경로는 확정되지 않았습니다.
  2. 최단경로가 확정되지 않은 점에서, 최단경로의 가중치가 제일 적은 정점을 고릅니다. 이 정점의 최단경로를 확정합니다.
  3. 최단경로가 확정된 점에서 갈 수 있는(간선이 연결된) 다른 정점의 최단경로의 가중치를 (현재 정점의 최단경로 + 간선의 가중치) 로 업데이트 해줍니다. 단, 이미 이보다 최단경로의 가중치가 작은 경우에는 업데이트 하지 않습니다.
  4. 모든 정점의 최단경로가 확정 되지 않았다면, 2로 돌아갑니다.

예를 들어 서울에서 시작해서 다른 모든 도시의 최단경로를 정한다면,

  1. 서울의 최단경로의 가중치를 0으로 표현합니다. 다른 모든 도시의 가중치는 무한입니다.
  2. 서울의 최단경로를 0으로 확정합니다.
  3. 인천, 부산, 대전의 최단경로의 가중치를 각 0+2000=2000, 0+80000=80000, 0+20000=20000으로 업데이트 합니다.
  4. 인천의 최단경로를 2000으로 확정합니다.
  5. 서울의 최단경로를 2000+3000=5000으로 업데이트 해야하나, 이미 더 짧은 최단경로를 찾았기 때문에 업데이트 하지 않습니다.
  6. 대전의 최단경로를 20000으로 확정합니다.
  7. 세종, 대구의 최단경로를 각각 20000+5000=25000, 25000+15000=35000으로 확정합니다.
  8. 세종의 최단경로를 25000으로 확정합니다. …

와 같은 방법으로 계속 반복합니다. 이 알고리즘은 올바릅니다. 왜냐하면, 가중치가 확정된 점에서, 다른 가중치를 확정하기 위해서는 확정되는 점에서 확정되지 않은 점으로 가는 가장 짧은 경로를 찾아야 하는데, 이는 간선 하나로만 이루어져있기 때문입니다. 여기서 가중치가 계속 무한으로 남아있으면 방문할 수 없는 정점입니다. 개성으로 가는 방법은 존재하지 않습니다.

이 알고리즘에서, 2번 부분을 $ O(log V) $에 처리하고, 3번 부분을 각 도시마다 $O(1)$ 에 처리하는 자료구조를 사용한다면 $ O(E + V log V) $의 시간이 소요되게 됩니다.

이 알고리즘의 pseudo-code 는 다음과 같습니다.

function Dijkstra(Graph, source):
	Q <- priority queue where minimum distance pops first
	foreach vertex v in Graph:
		dist[v] := Infinity

	dist[source] := 0
	add source to Q
	
	while Q is not empty:
		v <- pop vertex in Q with minimum distance
		if v is visited as mark: ignore v
		mark v as visited
		
		foreach vertex v in neighbor of u :
			dist[u] := min(dist[u], dist[v]+weight(v->u))

최단경로와 모델링

여기서 문제들을 최단경로로 모델링하는 방법은 정점을 상태로 나타내는 것이고, 간선을 상태의 변화로 나타내는 것입니다.. 도시에서 다른 도시에서 가장 싼 가격을 구하는 문제는 상태가 “내가 어느 도시에 있는가” 이고, 상태 변화는 “내가 어느 도시에서 다른 도시에 이동하는가” 이고, 이는 곧 상태변화를 의미합니다. 또한 상태 변화의 비용은 교통수단의 비용이므로 가중치입니다.

다음의 두 문제를, 최단경로 문제로 보이지 않는 문제를 한번 생각 해 봅시다.

  1. (Small Multiple) $ K $의 배수 중에서 십진수로 표현했을 때 자릿수의 합중 제일 작은 값을 구하여라. (7 * 143 = 1001 이므로, $ K = 7 $ 인 경우 답은 2이다. 7 * 1430 = 10010 처럼, 이런 수는 여러개가 존재할 수 있다.)

  2. (Linear Sum) 정수 $ a_1, a_2, \cdots, a_n $ 이 주어졌을 때, 음이 아닌 정수 $ c_1, c_2, \cdots, c_n $ 에 대해서, $ c_1 a_1 + c_2 a_2 + \cdots + c_n a_n $ 으로 $ X $를 표현할 수 있는가?

이 두 문제는 무엇을 정점으로 잡아야 할지, 무엇을 간선으로 잡아야 할지 굉장히 난해합니다. 이 두 문제를 풀어봅시다.

Small Multiple

이 문제에서, 모든 숫자들은 1에서 시작해서, 다음과 같은 작업을 0번 이상 해서 만들 수 있습니다.

  1. 숫자에 1을 더한다. 이 작업을 할 경우에는 자릿수의 합이 1 증가하게 됩니다. (마지막 자리가 9가 아닌 경우에 해당하지만, 중요하지는 않습니다.)
  2. 숫자에 10을 곱한다. 이 작업을 할 경우에 자릿수의 합은 변화하지 않습니다.

결국 상태는 각 숫자가 되고, 이 상태를 변화시키는 방법은 다음과 같습니다.

  1. $ x $ 에서 $ x+1 $ 로 변화시키는데 비용이 1 듭니다.
  2. $ x $ 에서 $ 10x $ 로 변화시키는데 비용이 0 듭니다.

그리고 어떤 숫자의 각 자릿수의 합은, 비용+1이 됩니다. 그럼 상태는 모든 숫자가 되고, 이것을 정점으로 무한한 그래프를 만들면

  1. $ x $ 에서 $ x+1 $ 로 가중치 1의 간선을 긋습니다.
  2. $ x $ 에서 $ 10x $ 로 가중치 0의 간선을 긋습니다.

이 중에서 $ K $ 의 배수중의 최단거리+1이 즉 $ K $의 배수중에서 자릿수의 합이 제일 작은 수 +1이 되고, 정답이 됩니다. 하지만 그래프가 무한하면 문제를 풀기 힘들기 때문에, 우리는 이 그래프를 압축할 수가 있습니다. 두 정점 $ x $와 $ y $가 $ K $로 나눈 나머지가 같을 경우에, 그래프의 형태는 같습니다. 그래서 이 그래프를 $ K $ 로 나눈 나머지 안에서 구성해주면 됩니다. 즉,

  1. $ x $ 에서 $ (x+1) \bmod K $ 로 가중치 1의 간선을 긋습니다.
  2. $ x $ 에서 $ 10x \bmod K $ 로 가중치 0의 간선을 긋습니다.

이렇게 그래프를 구성해 준 경우에, 1에서 0으로 가는 최단거리 +1이 정답이 되고, 숫자를 만드는 방법은 그래프의 경로를 따라가 주면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
int main() {
  int K; scanf("%d", &K);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
  vector<bool> vis(K+1);
  Q.emplace(0, 1);
  while(!Q.empty()) {
    int dist, node; tie(dist, node) = Q.top(); Q.pop();
    if(vis[node]) continue; vis[node] = true;
    if(node == 0) {
      printf("%d\n", dist+1);
      return 0;
    }
    Q.emplace(dist, node*10%K);
    Q.emplace(dist+1, (node+1)%K);
  }
}

Linear Sum

이 문제에서는 가능하다, 가능하지 않다. 라는 상태만 있고 비용에 대한 설명은 없습니다. 우리는 이 문제를 최단거리 문제로 변형해서 풀 것입니다.

우리는 다음과 같은 방법으로 숫자를 상태로 모델링 하여 만들 것 입니다. 이 그래프는 모든 0 이상 $X$ 이하의 정수들을 정점으로 가지고 있고, 정점 $ x $ 는 모든 $ i $ 에 대해서 $ x+a_i $ 로 가중치 $a_i$의 방향성이 있는 간선들이 그어져 있습니다. 0에서 도달할 수 있는 정점들은 $a_i$ 들의 합으로 표현이 가능하고, 그러면 $ X $ 가 도달 가능한 수 인지 (최단거리가 $X$ 인지) 판단하는데에, $ O(Xn) $의 시간이 들게 됩니다. $X$ 가 매우 큰 수라면 판단하기 힘들게 됩니다.

그래서 우리는 몇몇 사실들을 증명하고 최단거리로 알고리즘을 바꾸려고 합니다.

  1. 원래 그래프의 정점 $ X $ 에 도달할 수 있으면 $ X + a_1 $ 에도 도달할 수 있다.

이는 자명한 사실입니다. $ X $ 부터 $ X + a_1 $ 까지 간선이 그어져 있기 때문입니다.

  1. 정점을 $ a_1 $ 으로 나눈 나머지를 모두다 같은 정점으로 만들고(압축하고), 간선들을 남겨놓은 그래프에서 정점 $ X $ 에 도착하는 최단거리보다 작은 나머지가 $ X $ 인 숫자들은 표현하지 못하고, 크거나 같은 숫자는 표현할 수 있다.

이는 어떤 정점 $X$에서 최단거리보다 작은 숫자를 표현할 수 있다면, 원래 그래프의 성질에 의해서 그 정점에는 최단거리보다 작은 숫자의 거리를 이용해 도달할 수 있고, 가정에 모순입니다. 관찰 1을 사용하면, 크거나 같은 숫자를 사용할 수 있다는 사실은 자명합니다.

그래서 우리는 정점을 $ a_1 $ 으로 나눈 나머지만 남겨서, 간선을 그어 그래프를 만드는 것으로 주어진 수 $ X $ 를 $ a_1 $ 으로 나눈 나머지 까지 도착하는 최단거리보다 큰지 작은지의 여부만 가지고 Linear Sum으로 표현할 수 있는지 없는지를 알 수 있습니다.

pseudo-code

function LinearSum(X, a):
	dist <- array size of a[1], filled with Infinity
	Q <- priority queue where minimum distance pops first
	add 0 to Q
	while Q is not empty:
		v <- pop number in Q with minimum disance
		if dist[ v mod a[1] ] < v then ignore v
		dist [ v mod a[1] ] := v
		add v + x to Q foreach x in a

	return dist[ X mod a[1] ] >= X

결론

다양한 문제를 최단경로 문제로 바꾸는 방법을 써 봤습니다. 어떤 정보를 상태로 남기고, 사라지는 정보가 어떤 정보인지, 그리고 가중치를 어떻게 잡을지가 최단경로 문제에서 제일 중요합니다. 최단경로 문제는 최소 비용을 구하는 대부분의 문제에서 중요하게 작용을 하니, 중요한 정보들을 상태로 남기고, 기존의 알고리즘을 그대로 사용한다면 수월하게 문제를 풀 수 있을 것 입니다.