백준 11404 - 플로이드

 

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

11404번: 플로이드

플로이드 워셜 알고리즘을 활용한 기초 문제. 문제보단 알고리즘 자체에 대한 이해가 필요하다.

 

플로이드-워셜 알고리즘은 다익스트라 알고리즘처럼 모든 정점 사이의 최단 거리를 찾는 알고리즘이다. 두 알고리즘은 수행 가능 조건, 결과, 시간복잡도 등이 조금씩 다르다.

 

두 알고리즘의 비교

주어진 그래프의 특성에 따라 적절한 최단 경로 알고리즘을 선택해야 한다. 아직 배우지 않은 알고리즘은 배제했다.

 

예를 들어, 음수 가중치가 있을 경우 울며 겨자먹기로 플로이드-워셜 알고리즘을 선택할 수밖에 없다.

일반적인 그래프에서는 다익스트라 알고리즘이 훨씬 수행속도가 빠르겠지만, 정점의 개수에 비해 간선의 개수가 많을 경우 플로이드-워셜 알고리즘이 더 빠를 수 있다. 다익스트라 알고리즘은 한 번 수행했을 때 한 정점을 시작으로 하는 최단 거리밖에 구하지 못하므로, 전체 최단 경로를 구하려면 O(|E| + |V| log |V|)의 연산을 |V|번 반복해야 하기 때문이다.

 

무엇보다 플로이드-워셜 알고리즘은 개념 이해보다 구현이 훨씬 간단하다는 장점이 있어, 작은 그래프에서 사용하기에 좋을 듯 하다. 그럼 개념을 간단하게 설명하고 구현을 통해 이해해보자.

 

플로이드-워셜 알고리즘은 동적 계획법을 이용하는 알고리즘이다. 즉 이전에 계산해둔 값을 활용한다. 그래프에서 각 정점의 순서쌍 <u, v>에 대해 최단 경로를 찾는다. u에서 v로 가는 최단 거리는 당연하게 u에서 v로 가는 모든 경로 중 최단 거리를 말한다. 모든 경로란, u와 v를 직접 연결하는 간선의 거리, 또는 다른 정점을 경유하는 거리들 중 실제 경로가 존재하는 거리일 것이다.

 

여기서 '다른 정점을 경유하는 거리'에 대해 더 자세히 알아보자. 경유하는 정점의 범위가 어떠한가? 가 이 알고리즘의 핵심이다. 첫 반복에서는 모든 순서쌍 <u,v>에 대해, 1번 정점만 경유 가능할 경우의 최단 거리를 계산한다. 코드로 나타내보자.

 

for(i=1;i<=V;i++)
	for(j=1;j<=V;j++)
		graph[i][j] = min(graph[i][j], graph[i][1] + graph[1][j]);
        			//직접 연결하는 간선   //1번 간선을 경유하는 경로

 

다음 반복에서는 1,2번 정점을 경유할 수 있다. 그런데 생각해보면, 이전의 반복문을 통해 graph[i][j]에는 '직접 연결', '1번 경유' 중 더 작은 값이 저장되어있다. 따라서 현재의 반복문에서는 '직접 연결', '1번 경유', '2번 경유' 3개를 비교할 필요 없이, 현재 graph[i][j]에 저장된 값과 '2번 경유'만 비교하면 된다! 여기서 동적 계획법이 활용되는 것이다.

 

for(i=1;i<=V;i++)
	for(j=1;j<=V;j++)
		graph[i][j] = min(graph[i][j], graph[i][2] + graph[2][j]);
        //이럴 필요 없음!!
        //graph[i][j] = min(graph[i][j], graph[i][1] + graph[1][j], graph[i][2] + graph[2][j]);

 

이제 삘이 올 것이다. 매 반복마다, 경유 가능한 정점의 범위를 1씩 증가시키면서 위의 코드를 반복한다.

 

for (k = 1; k <= V; k++)
    for (i = 1; i <= V; i++)
	for (j = 1; j <= V; j++)
		graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);

딱히 머리를 굴리지 않아도 위 코드의 시간복잡도가 O(|V| ^ 3)임을 알 수 있다. 심지어 k, i, j 순으로 중첩되는 이 삼중 반복문 하나가 플로이드-워셜 알고리즘의 전부이다. 다들 나처럼 알고리즘의 이름만 보고 겁먹지 말자.