플로이드 와샬

[daeunkwak]

[플로이드 와샬(Floyd-Warshall)]

✅ 최단거리 알고리즘

• 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는데 사용되는 알고리즘
• 모든 정점을 한 번에 갱신하면서 거리를 계산하는 방식
• 따라서 가중치가 변하는 경우에도 다시 계산할 필요가 없음
• 시간복잡도 O(N^3)

✅ 기본 아이디어

1. 모든 정점 쌍 사이의 최단거리를 저장할 배열 준비 > 값 무한대로 초기화
2. 3개의 중첩 반복문 사용 > 각각의 정점을 경유지로 가정함
3. 경유지를 거쳐서 가는 경우, 거치지 않고 바로 가는 경우 비교 > 짧은 경로 선택
4. 모든 정점을 경유지로 시도하여 모든 쌍 간의 최단 경로 찾기

✅ ex1. 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

• n명의 권투선수 1~n
• A 선수가 B 선수보다 실력이 좋다면 항상 이김
• 주어진 경기 결과로 정확하게 순위를 매길 수 있는 선수의 수 return

1. A → B, B → C 이면 A → C 법칙을 사용하기 위해 선수를 노드로 간주함 > 각 선수가 모든 선수를 거쳐가서 간접적으로 이길 경우를 찾으면 된다.
2. i에서 j로 갈 수 있는지 판단 > 근데 k를 거쳐서 갈 수 있는지 판단하는 경우
   1. graph[i][k] ≠ INF && graph[k][j] ≠ INF > 갈 수 있다고 판단
   2. Math.min(graph[i][j], graph[i][k] + graph[k][j]); > 최단거리 구하기

import java.util.*;

public class Solution {

    public int solution(int n, int[][] results) {
        int answer = n;
        int INF = n * n;
        
        // 그래프 초기화
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
				
				// 그래프에 result값 반영
        for (int[] result : results) {
            graph[result[0] - 1][result[1] - 1] = 1;
        }

        // ** 플로이드 와샬 알고리즘 **
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

				// answer 만들기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }

                if (graph[i][j] == INF && graph[j][i] == INF) {
                    answer--;
                    break;
                }
            }
        }

        return answer;
    }
}

---

참고

https://bellog.tistory.com/174