[자료구조] 14-3. 넓이 우선 탐색 알고리즘의 응용 (2)

저번 시간엔 한 버텍스에서 시작해 다른 모든 버텍스로 가는 최단 경로 알고리즘을 배웠다. 이번엔 모든 버텍스들에 대한 최단 거리를 찾는 법을 알아본다.

즉, 이 문제는 모든 버텍스의 쌍인 u와 v 사이의 최단 거리를 찾는 문제다. 사실 이것은 하나의 출발점에서 모든 버텍스까지의 최단거리를 확장한 문제라고 생각할 수 있다. 모든 버텍스에 대해 dijkstra's 알고리즘을 돌리면 되지 않을까?

그럴 수도 있겠지만, 새로운 알고리즘을 floyd 라는 사람이 제안했다. 그리고 이후에 여러 번 개선되면서 floyd-warshall 알고리즘과 같이 다양한 이름이 붙여졌다.

이 문제는 주어진 그래프에 대한 인접 행렬을 입력으로 받는다. 왼쪽 그래프가 있다면 오른쪽과 같은 인접 행렬을 받는 것이다. 예를 들어 인접 행렬에 있는 4는, 버텍스 0과 1로 가는 가중치이다.

 가운데와 같은 인접 행렬을 입력으로 받아서 오른쪽과 같은 아웃풋을 만들어낸다. 모든 버텍스들 사이에서 최단 거리가 저장도니 매트릭스를 만들어내는 것이다.

따라서 출력은 최단 거리를 저장한 행렬이 된다. G[u][v]는 버텍스 u에서 버텍스 v까지 가는 최단 거리를 의미한다. 이 알고리즘은 음수의 가중치를 가진 엣지에서도 적용이 가능하다.

하지만 가중치가 음수인 순환 경로가 존재하는 경우에는 작동하지 않는다. 돌면 돌수록 음수가 더해져 값이 계속 감소해 최단 경로가 존재하지 않게 되기 때문이다.

이렇게 모든 쌍의 최단 경로를 찾는 알고리즘을 동적 프로그래밍이라고 한다.

동적 프로그래밍이란, 주어진 문제를 여러 개의 작은 문제로 분할하고, 그 문제의 합을 통해서 최종 답을 찾는 알고리즘이다.

예를 들어, A에서 F까지 가는 최단 경로 비용을 구해보자. 살펴보면 A에서 가려면 B와 C 두 개의 길만 존재한다. B를 선택하면 F까지 가는데에는 뚜렷한 경로가 존재한다. 따라서 A-B의 코스트 + B-F 까지의 콧트를 더하면 된다. C의 경우도 마찬가지다.

이것은 A에서 F까지 가는 경로의 최단 비용을 찾아야 하는 문제를 더 작게 쪼갠 것이다. 쪼갠 것을 또 쪼개면 재귀적으로 표현이 될 것이다. 이 작은 문제들의 합 중에서 최적의 합을 찾는 것이 동적 프로그래밍 알고리즘이다.

이 방법을 floyd 알고리즘에 적용해보자. floyd에서는 A^k[i][j]로 버텍스 사이의 경로를 표현한다. i부터 j까지 가는 경로의 최단 비용이라는 의미이다. 

- 버텍스는 0부터 n-1까지 커지기 때문에 이 그래프에서 인접 행렬은 -1이라는 인덱스를 이용해서 표현한다.

- k는 i부터 j 까지 가는 버텍스 중에 k보다 작거나 같은 버텍스만 지나가는 경로를 고려하겠다는 의미이다. 예를 들어, i a b j 순이라면, a와 b는 k보다 작거나 같아야 한다.

두 버텍스 사이에 엣지의 가중치가 입력으로 주어지고, 그때 인덱스는 -1을 사용한다면 이 그래프와의 인접 행렬은 오른쪽 아래처럼 주어진다. 여기서 보면 2번 버텍스에서 1번 버텍스로 가는 경로는 존재하지 않는다. 그런 경우에는 무한대를 저장하도록 한다.

floyd 알고리즘은 동적 프로그래밍 방법을 따르므로, 작은 문제의 합을 이용해 큰 문제를 해결해 나갈 것이다. 여기서 제일 작은 문제는 A0가 될 것이다. A0를 고려하고 또 다음 1번 2번...마지막 n번 버텍스까지 고려하는 최단 거리를 구하면 된다.

A^k[i][j] 즉, i에서 j까지 가면서, k보다 작거나 같은 버텍스를 지나는 경로를 생각해보자. 경로에 있는 버텍스들을 k보다 인덱스가 작은 것과 큰 것으로 나눌 수 있을 것이다.

그럼 비용은 어떻게 구할 수 있을까? k보다 작거나 같은 버텍스를 지나는 경로와 k를 지나는 경로(단, k보다 작거나 같은 버텍스만 지나면서)를 비교한다. 즉, k까지 갔다가, k에서 j까지 가는 비용의 합 중에서 더 작은 값을 선택한다.

이 과정은 edge relaxation과 닮았다. k를 지나지 않는 값을 k을 지나는 값과 비교해서 더 작은 값으로 바꾸는 개념이기 때문이다. 따라서 floyd 알고리즘은 동적 프로그래밍을 이용하지만, dijkstra 알고리즘의 개념을 받아들어고 있다고 할 수 있다.

구현 방법은 굉장히 단순하다. for 루프가 3번 중첩되어 있다. k는 0부터 n까지 즉, k를 증가시켜 나가면서 모든 버텍스 쌍에 edge relaxation을 수행한다. 

dijkstra 알고리즘은 피보나치 힙 먼저 구현해야해서 생소하고 복잡하지만, floyd는 비교할 수 없을 정도로 단순하다. dijkstra 알고리즘을 n번 돌리는 생각보다 훨씬.

시간 복잡도는 n개짜리 for 루프를 3번 돌기 때문에 O(n^3)이라고 할 수 있다. 시간은 더 걸리지만 구현이 단순한 것이 장점이다.

floyd 알고리즘의 예를 들어보자. 위의 그래프를 인접 행렬로 만들면 가운데와 같다. 인덱스는 -1로 주기로 했으므로 A^-1이다. 엣지가 없는 곳은 무한대 자기 자신은 0이다.

A^-1 을 받아서 A0를 계산한다. 즉, 0번보다 작거나 같은 버텍스를 지나는 경로를 고려한다. 그 다음으로 1번보다, 2번 보다 작거나 같은 버텍스를 지나는 경로를 계산하면 최종 답이 나온다.

A^-1에서 A0로 가는 과정을 생각해보자. A0라는 것은 i에서 0번을 통해 j를 가는 경로와 그렇지 않은 경로를 비교하라는 것이다.

0번을 지나가는 경로이기 때문에 0을 시작 또는 끝으로 하는(0을 포함하는) 경로는 고려할 필요가 없다. 또한, 자기 자신은 항상 0이다. 따라서 우리가 고려해야 할 대상은 남은 빈칸 두 개다.

1. A^0[1][2]: 1번에서 시작해서 2번으로 끝나는 경로

2. A^0[2][1]: 2번에서 시작해 1번으로 끝나는 경로

1번에서 시작해서 2번에서 끝나는데 0보다 작거나 같은 버텍스를 지나는 비용 A^0[1][2] 는

- A^-1[1][2]: 1번에서 2번으로 끝나는데 0번을 고려하지 않는 값 = 2

- 1번에서 0번으로 갔다가(A^-1[1][0]=6) 0번에서 1번으로 가는데 0번을 고려하지 않는(A^-1[0][1]=11) 값

중에서 더 작은 값을 선택한다.

그런데 가운데의 행렬에서는 2이므로 바뀌지 않고 그대로 2로 간다.

A^0[2][1]을 구하면,

- 2에서 1로 가는 값 A^-1[2][1] = 무한대

- 2에서 0으로 가는 값 A^-1[2][0] =3, 0에서 1로 가는 값 A^-1[0][1] = 4 를 더하면 7 

따라서 원래의 무한대 보다 작으므로 7로 바뀐다.

따라서 2와 7을 넣은 것이 최종 A^0의 매트릭스가 된다.

A^0[0][2] = 11

A^0[0][1] + A^0[1][2] = 4+2 = 8

8이 더 작으므로 8로 갱신된다.

A^0[2][0] = 3

A^0[2][1] + A^0[1][0] = 7+6

원래 값이 더 작으므로 3으로 간다.

i에서 2를 지나 j로 가는 것이므로 2로 시작하고 끝나는 건 제외하고 푼다.

A^1[0][1]= 4

A^1[0][2] + A^1[2][1] = 6+7

4가 더 작으므로 4로 유지된다.

A^1[1][0]= 6

A^1[1][2] + A^1[2][0] = 2+3 = 5

5로 갱신된다.

이것이 최종 아웃풋이다. 원소는 해당 버텍스에서 다른 버텍스로 가는 최단 경로 코스트다.