[GDG - 스터디] 플로이드 워셜을 이용하여 최단 경로 찾기 (cf. DP)

플로이드 워셜

플로이드-워셜(Floyd-Warshall) ?

• 각각의 모든 노드에 대하여 다른 모든 노드로의 최단 거리를 구할 수 있는 알고리즘 ! ↔ 특정 시작점에서 다른 모든 노드로의 최단 거리를 구하는 다익스트라, 벨만-포드 알고리즘
• 음수 가중치를 갖는 간선이 있어도 수행 가능하나, 음수 사이클이 있는 경우엔 사용할 수 없다.

---

💡 플로이드 워셜 핵심 개념 - 동적 계획법(DP)

• DP는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 후에, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하기 위한 알고리즘이다 ! → **기억하며 풀기**(Memoization)
  1. 메모이제이션 : 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고, 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결한다.
  2. 점화식 만들기 : 변수 간의 관계식을 만드는 것이라고 보면 된다. ( ex: 피보나치 수열 f(n) = f(n-1) + f(n-2) )

<aside> 💡

DP를 적용시킬 수 있는 조건 ?

1. 중복되는 부분 문제 (Overlapping Sub-problems)

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구하기 때문에, 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능한 것 !

1. 최적 부분 구조 (Optimal Substructure)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다 ! </aside>
• DP 문제 해결 방식
  • Bottom-Up → 반복문 사용(최적 부분 구조 보장)
  • Top-Down → 재귀 사용(Memoization 활용)

---

💡 플로이드 와샬 - 구현

• 시간 복잡도: O(V^3) → 노드 수(V)가 작을 경우 효율적이다. ( 일반적으로 V ≤ 500 정도가 적합하다고 한다. )
• 2차원 배열에 모든 노드에 대하여 다른 모든 노드로의 최단 거리를 저장한다. → 중간 노드를 고려하여 경로를 점진적으로 최적화해나간다. ( dist[i][j] : 노드 i에서 노드 j로 가는 최단 경로의 비용 )
  1. 배열(dist[i][j])을 선언하고 초기화 한다. → i == j인 경우엔 최단 경로를 0으로, 이외의 경우엔 INF로 초기화한다.
  2. 출발 노드는 u, 도착 노드는 v, 이 간선의 가중치는 w라고 했을 때, dist[u][v] = Math.min(dist[u][v], w)로 주어진 그래프 정보를 업데이트한다. ( min으로 중복 간선 처리 )
  3. DP를 이용해 작은 문제(경로에 중간 노드 포함)를 점진적으로 해결해나간다.
• 점화식
• $$ dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j]) $$
• 다익스트라, 벨만-포드 알고리즘에서는 INFINITY값을 Integer.MAX_VALUE로 초기화했지만, 플로이드-워셜 알고리즘에선 INF 값에 어떤 수를 더한 값을 비교하게 될 수 있기 때문에 10억 정도의 적당히 큰 수로 초기화 한다.

import java.util.*;
import java.io.*;

public class FloydWarshall {
    static final int INF = 100000000; // 무한대 값
    static int[][] dist; // 최단 거리 저장 배열
    static int n, m; // 노드 수, 간선 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 노드 수와 간선 수 입력
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 최단 거리 배열 초기화
        dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        // 간선 정보 입력 및 초기화
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken()); // 가중치
            dist[u][v] = Math.min(dist[u][v], w); // 중복 간선 처리
        }

        // 플로이드-워셜 알고리즘 수행
        floydWarshall();
    }

    public static void floydWarshall() {
        for (int k = 1; k <= n; k++) { // 중간 노드
            for (int i = 1; i <= n; i++) { // 시작 노드
                for (int j = 1; j <= n; j++) { // 도착 노드
                    if (dist[i][k] != INF && dist[k][j] != INF) { // 경로가 존재하는 경우
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }
}

---

문제: 운동 (백준 1956)

문제 링크

 

---

알고리즘 [접근 방법]

• 주어진 간선 정보들로부터 가중치 값의 합이 가장 작은 사이클을 찾는 문제이기 때문에, 모든 노드 쌍의 최단 거리를 계산해야 할 필요가 있기에 플로이드-워셜 알고리즘을 사용하면 된다.

---

해결 코드

• 이 문제는 주어진 그래프에 대해 플로이드-워셜 알고리즘을 수행하고, dist[i][i]의 값들 중에 가장 작은 값을 출력하면 된다. → 일반적인 경우(자기 자신으로 가는 간선 X)에 자기 자신으로 가는 가중치 값이 0으로 초기화되지만, 이 문제에선 자기 자신으로 가는 가중치 값이 0으로 초기화해선 안된다 !

import java.util.*;
import java.io.*;

public class Main {
    
    static final int INF = 100000000;
    static int[][] dist;
    static int V, E;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        // 최단 거리 배열 초기화
        dist = new int[V + 1][V + 1];
        for (int i = 1; i <= V; ++i) {
            Arrays.fill(dist[i], INF);
            // dist[i][i] = 0; // 이 문제에선 자기 자신으로 가는 비용이 0이 아닐 수 있다.
        }
        
        // 간선 정보 입력 및 초기화
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            dist[u][v] = Math.min(dist[u][v], w); // 중복 간선 처리
        }
        
        floydWarshall();
        
        // 최소 사이클 찾기
        int minCycle = INF;
        for (int i = 1; i <= V; i++) {
            if (dist[i][i] < minCycle) {
                minCycle = dist[i][i];
            }
        }

        // 결과 출력
        if (minCycle == INF) {
            System.out.print("-1");
        } else {
            System.out.print(minCycle);
        }
    }
    
    public static void floydWarshall() {
        for (int k = 1; k <= V; ++k) {
            for (int i = 1; i <= V; ++i) {
                for (int j = 1; j <= V; ++j) {
                    if (dist[i][k] != INF && dist[k][j] != INF) { // 중간 경로가 존재하는 경우
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }
}

---

정리

• 각각의 모든 노드에 대하여 다른 모든 노드로의 최단 거리를 구해야 하는 경우엔 플로이드-워셜 알고리즘을 사용하자 ! ( ex: 최소 가중치값의 합을 갖는 사이클을 찾아야 하는 경우 )
• 이 알고리즘을 사용할 땐 음수 가중치가 있어도 괜찮지만, 음수 사이클이 존재해선 안된다 !

 

https://thin-azimuth-2a9.notion.site/GDG-cf-DP-148f4ee21c00805ab86bdc990c4ba254?pvs=4