안녕하세요 오늘은 플로이드-워셜 알고리즘에 대해 알아보도록 하겠습니다. 플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 O(노드 수^3)의 시간 복잡도를 가집니다. 또한 벨만-포드 알고리즘과 유사하게 음수 가중치 간선이 있어도 수행이 가능합니다. 하지만 벨만-포드 알고리즘과의 차이점은 그래프에서 시작점을 지정하기 않고 모든 노드 간의 최단 경로를 탐색한다는 점입니다. 동적 계획법 원리를 이용해 접근하기 때문에 모든 노드의 최단 경로를 탐색할 수 있으며 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 개념을 응용합니다.
플로이드-워셜 알고리즘의 동작 방식은 다음과 같습니다.
1. dp 배열을 선언하고 초기화 : dp[S][E] = 노드 S에서 E까지의 최단 거리
- 이 때 S==E인 칸은 0으로, 다른 칸은 충분히 큰 값으로 초기화
- dp 배열에 그래프 데이터 저장 : dp[S][E] = W
- W : 노드 S에서 노드 E로 이동하는 간선의 가중치
- 점화식으로 배열 업데이트 : dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j])
- 3중 for문의 형태로 반복(K,S,E 순서 / 각각 1부터 N까지 반복)
백준 11404 (플로이드) 문제를 통해 플로이드-워셜 알고리즘을 구현해보겠습니다. N개의 도시가 있을 떄 한 도시에서 출발해서 다른 도시로 도착하는 M개의 버스가 있을 때 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제입니다. 모든 도시의 비용의 최솟값을 구해야 하므로 플로이드-워셜 알고리즘을 사용합니다.
import java.util.*;
import java.io.*;
class Main{
static int N,M;
static long[][] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
dp = new long[N+1][N+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i==j) dp[i][j] = 0;
else dp[i][j] = Integer.MAX_VALUE;
}
}
for(int i=0;i<M;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
dp[s][e] = Math.min(dp[s][e], v);
}
for(int k=1;k<=N;k++){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(dp[i][j] == Integer.MAX_VALUE) System.out.print("0 ");
else System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
}플로이드-워셜 알고리즘은 노드의 수가 적을 때 모든 노드의 최단 경로를 구하는 문제에서 사용됩니다. 플로이드-워셜 알고리즘은 노드 수^3의 시간 복잡도를 가지기 때문에 노드 수가 크다면 사용하기 어렵다는 단점이 있어 제한 조건을 잘 살펴봐야 합니다.
백준 11403 (경로 찾기) 문제의 경우 모든 정점에 대해 i에서 j로 가는 길이가 양수인 경로가 존재하는지를 조사하는 문제입니다. 플로이드 워셜 알고리즘의 특징을 이용하여 dp[i][k] == 1이고 dp[k][j] == 1일 경우 i와 j는 연결되어있다라는 명제를 도출할 수 있고, 이를 통해 연결 여부를 확인합니다.
백준 1389(케빈 베이컨의 6단계 법칙) 문제의 경우 유저와 친구 관계가 주어졌을 때 케빈 베이컨의 수가 가장 작은 사람을 출력하는 문제입니다. 이 문제는 인접 리스트로 구현한 후 BFS를 이용하여 풀 수 있으나 노드 수가 작기 때문에 플로이드-워셜 알고리즘을 사용할 수 있습니다. 플로이드-워셜 알고리즘을 사용하여 dp 배열을 채운 후 dp 배열의 각 행의 합인 케빈 베이컨 수를 각 행의 합의 최솟값을 가지는 행 번호를 출력합니다.
