❒ Description
프로그래머스 Lv3. 순위 문제를 풀면서 알게된 Floyd Warshall 알고리즘에 대해서 학습하자.
❒ Floyd Warshall 알고리즘
Floyd warshall 알고리즘은 모든 노드간의 최단 경로 탐색이 필요한 경우에 사용한다.
음의 가중치가 있어도 사용할 수 있으며, O(v³)의 시간 복잡도를 갖는 알고리즘이다.
Floyd warshall 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다.
거쳐가는 정점을 A로 하게 경로는 `C → A → B`, `B → A → C`, `D → A → C`, `D → A → B`로 총 4개가 된다.
※ 참고 블로그
https://blog.naver.com/ndb796/221234427842
https://sh1mj1-log.tistory.com/151
❒ Java로 구현하기
Java 코드는 아래의 순서로 구현하면 된다.
i. 인접행렬 만들기
ii. 각 노드간의 최단 거리 인접행렬 update
iii. 3중 for문을 순회하며 인접행렬 update
위 순서를 적용하여 백준: 플로이드 문제를 풀어보자.
// i. 인접행렬 만들기
int INF = 1000000000;
int[][] distance = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
distance[i][j] = 0;
} else {
distance[i][j] = INF;
}
}
}
// ii. 각 노드간의 최단 거리 인접행렬 update
for (int i = 0; i < m; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
int weight = sc.nextInt():
distance[start][end] = Math.min(distance[start][end], weight);
}
// iii. 3중 for문을 순회하며 인접행렬 update
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
}
}
}
3중 for문으로 구성되어 있는 iii 번째 코드가 핵심이다.
k | 중간 노드 |
i | 출발 노드 |
j | 도착 노드 |
K가 중간 노드인데 왜 가장 첫 번째 for문에 위치한 이유는 중간 노드인 K는 항상 고정되어 있어야 하기 때문이다.
즉, 중간 노드 k를 고정한 상태에서 출발 노드 i와 도착 노드 j에 대해 경로를 확인해야 하기 때문이다.
그리고 `i → j`의 거리와 `i → k` + `k → j`거리를 비교하여 더 짧은 거리를 distance 인접 행렬에 update한다.
이는 Floyd Washall 알고리즘의 점화식을 그대로 구현한 것이다.
※ 점화식 : D₁₃ = min(D₁₃, D₁₂ + D₂₃)
'Algorithm > 내용 정리' 카테고리의 다른 글
Height-Balanced(높이 균형) Binary Tree (0) | 2024.09.22 |
---|---|
Dijkstra & Floyd-Warshall (0) | 2024.09.17 |
Dijkstra 알고리즘 (0) | 2024.09.10 |
위상 정렬(Topological Sorting) (0) | 2024.08.30 |
Circular Deque의 두 가지 구현 (0) | 2024.08.05 |