[백준] 11404 플로이드

들어가기

• 11404. 플로이드는 모든 노드간의 최단 거리을 구하는 문제입니다
• 시작과 도착이 같은 노드의 입력 값은 없으므로 Loop는 없습니다.
• 비용의 입력값이 자연수이므로 음수의 비용도 없습니다.
• 그러므로 제목 그대로 플로이드 와샬 알고리즘으로 푸는 문제입니다. 

 

플로이드-와샬 알고리즘

• 플로이드 와샬 알고리즘은 3중 for을 바탕으로 동작합니다.
• 노드 간의 최소 비용을 기록합니다.
• 최소 비용을 기록하여 재사용하기 때문에 DP입니다.
• 3중 for을 바탕으로 계산하기 때문에 복잡도는 O(n3)입니다.
• 아래는 기본이 되는 플로이드 - 와샬 코드입니다.
• 동일한 노드(i -> i)를 방문하는 경우,
• 노드 사이 간선이 없을 경우(여기서는 MAX_COST로 나타냈습니다)를 제외하면
• i -> j의 노드 사이에 k 노드를 두어 i -> k + k -> j로 가는 최소 비용으로 계산을 합니다.

for (int k = 0; k <= N; k++) 
for (int i = 0; i <= N; i++) 
for (int j = 0; j <= N; j++) {
	if ( i == j || i == k || k == j) continue;
	if (cost[i][k] == MAX_COST || cost[k][j] == MAX_COST ) continue;
	if (cost[i][j] > cost[i][k] + cost[k][j]) cost[i][j] = cost[i][k] + cost[k][j];
}