📑 목차
❓플로이드 와샬 정의
💁🏻♀️ 플로이드 와샬 과정
✨ 문제에 적용해보기
우선, 이 블로그를 보며 공부했던 내용을 정리한 글이라는 점을 말씀드립니다! 🙂
❓플로이드와샬 정의
→ '거쳐가는 정점'을 기준으로 최단 거리를 구하는 알고리즘입니다.
그렇다면, 다익스트라와는 어떤 점이 다를까요?
다익스트라 vs 플로이드 와샬의 차이점
다익스트라 : 하나의 정점에서 출발했을 때에 다른 모든 정점으로의 최단 경로를 구하는 알고리즘, 모든 정점에서 출발했을 때를 보는 알고리즘
플로이드 와샬 : '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶을 때 사용하는 알고리즘입니다. '거쳐가는 정점'을 기준인 점이 가장 다릅니다.
💁🏻♀️ 플로이드 와샬 과정
-
예시로, 가중치를 가진 유향 그래프가 이렇게 있다고 생각해봅시다.
-
1의 사진에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열로 나타내면 아래 사진과 같습니다.
아래 사진은 '현재 계산된 최소 비용'인데 이 상태에서 플로이드 와샬을 통하여 거쳐가는 정점을 기준으로 최단 거리를 구할 것 입니다 🙂
3. 이때, X에서 Y로 가는 최소 비용 vs X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용을 비교하면 됩니다.
3-1. 1를 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산하면 됩니다.
D[2,4]의 값은 D[2,4] vs (D[2,1] + D[1,4]) 중에서 더 작은 값으로 교체됩니다.
무한 vs 15가 되므로 15로 갱신됩니다.
- 노드 2를 거치는 경우
- 이렇게 3, 4까지 계산하여 갱신하면 최단 거리가 나오게 됩니다.
수정해야할 부분이 있거나 보완해야하는 사항이 있다면 언제든지 말씀해주세요!
✏️ 플로이드 와샬을 사용할 수 있는 알고리즘 문제들
✨ 문제에 적용해보기
이 중, 경로 찾기라는 문제에 플로이드 와샬을 적용해봅시다.
경로 찾기 문제는 무향그래프에서 갈 수 있는 경로가 있다면 1로 변경, 아니라면 0으로 두는 문제입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_11403_경로찾기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int arr[][] = new int[N + 1][N + 1];
int d[][] = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
d[i][j] = arr[i][j];
}
}
//이 부분이 플로이드 와샬의 핵심 부분 :)
//k=거쳐가는 노드
for(int k = 1; k<=N; k++) {
//i=출발 노드
for(int i=1; i<=N; i++) {
//j=도착하는 노드
for(int j = 1; j<=N;j++) {
if(d[i][k]+d[k][j]>1&&d[i][j]==0) {
d[i][j] = 1;
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
System.out.print(d[i][j]+" ");
}
System.out.println();
}
}// end of main
}// end of class이렇게 배열을 입력받아 노드의 갯수만큼 for문(플로이드 와샬)을 해주었더니 풀린 문제였습니다 🙂
📕 Reference
