[Algorithm] 플로이드-워셜 알고리즘

in Algorithm

플로이드-워셜 알고리즘에 대해 정리해보았습니다.

  1. 플로이드-워셜이란?
  2. 핵심 개념 이해하기
  3. k, i, j의 의미
  4. 동작 과정 시각화
  5. 코드 구현
  6. 시간복잡도와 공간복잡도
  7. 다익스트라와의 비교
  8. 실전 문제 적용

🎯 1️⃣ 플로이드-워셜이란?

💡 한 문장 정의

“모든 정점 쌍 사이의 최단 경로를 한 번에 구하는 알고리즘”

💡 언제 사용하는가?

  • “A 도시에서 B 도시로 가는 최단 거리는?” → 모든 도시 쌍에 대해 물어볼 때
  • “경유지를 거쳐가는 것이 더 빠른가?” → 중간 노드를 허용하며 최적 경로를 찾을 때
  • 그래프의 모든 쌍 최단 거리를 구해야 할 때

💡 특징

특징설명
시간복잡도O(V³) - 정점 개수의 세제곱
공간복잡도O(V²) - 2차원 배열
음수 간선처리 가능 (단, 음수 사이클은 불가)
그래프 종류방향/무방향 모두 가능
구현 난이도매우 쉬움 (3중 for문)

🧠 2️⃣ 핵심 개념 이해하기

💡 알고리즘의 본질

"도시 i에서 도시 j로 갈 때,
k번 도시를 중간에 한 번 거쳐도 되는지를
매 단계마다 허용해가며 최소 비용을 갱신하는 알고리즘"

💡 dist[i][j]의 의미

dist[i][j] = 지금까지 허용된 중간 도시들만 이용해서
             i → j로 가는 최소 비용

여기서 “지금까지 허용된”이 핵심이다. k값에 따라 허용 범위가 달라진다.

💡 동적 계획법(DP)으로서의 플로이드-워셜

플로이드-워셜의 본질적인 점화식:

DP[k][i][j] = 중간 도시를 1~k까지만 써서 i→j로 가는 최소 비용

DP[k][i][j] = min(
    DP[k-1][i][j],           // k를 거치지 않는 경우
    DP[k-1][i][k] + DP[k-1][k][j]  // k를 거치는 경우
)

실제 코드는 3차원 배열 대신 2차원 배열을 덮어쓰면서 k 단계를 확장한다.

🔑 3️⃣ k, i, j의 정확한 의미

💡 기본 구조

for (int k = 1; k <= n; k++) {        // 중간 노드
    for (int i = 1; i <= n; i++) {    // 출발 노드
        for (int j = 1; j <= n; j++) { // 도착 노드
            dist[i][j] = Math.min(
                dist[i][j],
                dist[i][k] + dist[k][j]
            );
        }
    }
}

💡 각 변수의 의미

변수의미역할
k중간에 거쳐도 되는 도시 번호k=1일 때는 1번만, k=2일 때는 1,2번까지 허용
i출발 도시모든 출발지를 순회
j도착 도시모든 도착지를 순회

💡 핵심 로직의 의미

dist[i][j] = Math.min(
    dist[i][j],          // 원래 알고 있던 i → j 최단 경로
    dist[i][k] + dist[k][j]  // i → k → j로 가는 새로운 경로
);

이 코드가 묻는 질문:

"i에서 j로 바로 가는 게 낫나?"
"아니면 k를 한 번 들렀다 가는 게 낫나?"

시각적 표현:

i ─────────▶ j  (직접)
│
│
▼
k

💡 왜 k가 가장 바깥 루프인가?

// ✅ 올바른 순서
for k
  for i
    for j

// ❌ 잘못된 순서
for i
  for j
    for k

이유: k는 “중간 도시로 k까지 허용한 상태에서 모든 i→j 최단거리를 갱신”한다는 의미다. 만약 i나 j가 바깥에 있으면 아직 허용되지 않은 중간 도시를 사용하게 되어 DP의 단계적 의미가 깨진다.

📊 4️⃣ 동작 과정 시각화

💡 예시 그래프

    1 ──(4)── 2
    │         │
   (3)       (2)
    │         │
    3 ──(5)── 4

💡 초기 상태 (k = 0, 중간 노드 허용 안 함)

dist[i][j] = 직접 연결된 간선만 사용

      1    2    3    4
1  [  0    4   INF  INF ]
2  [  4    0   INF   2  ]
3  [ INF  INF   0    5  ]
4  [ INF   2    5    0  ]

💡 k = 1 (1번 노드를 중간에 사용 가능)

"1번을 거쳐가면 더 빠른 경로가 있나?"

i=2, j=3일 때:
dist[2][3] = min(INF, dist[2][1] + dist[1][3])
           = min(INF, 4 + INF) = INF

i=3, j=2일 때:
dist[3][2] = min(INF, dist[3][1] + dist[1][2])
           = min(INF, INF + 4) = INF

💡 k = 2 (1,2번 노드를 중간에 사용 가능)

"2번을 거쳐가면 더 빠른 경로가 있나?"

i=1, j=4일 때:
dist[1][4] = min(INF, dist[1][2] + dist[2][4])
           = min(INF, 4 + 2) = 6

💡 최종 결과 (k = 4, 모든 노드 허용)

      1    2    3    4
1  [  0    4    8    6  ]
2  [  4    0    7    2  ]
3  [  8    7    0    5  ]
4  [  6    2    5    0  ]

💻 5️⃣ 코드 구현

💡 기본 템플릿

class FloydWarshall {
    static final int INF = 987654321;  // 충분히 큰 값

    public void solution(int n, int[][] graph) {
        int[][] dist = new int[n + 1][n + 1];

        // 1. 초기화

        // 2. 간선 정보 입력

        // 3. 플로이드-워셜 알고리즘
        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]);
                    }
                }
            }
        }

        // 4. 결과 출력
        printDistances(dist, n);
    }
}

📈 6️⃣ 시간복잡도와 공간복잡도

💡 시간복잡도

연산복잡도설명
플로이드-워셜O(V³)3중 for문
초기화O(V²)2차원 배열 초기화
전체O(V³)플로이드-워셜이 지배적

💡 공간복잡도

자료구조크기설명
거리 배열O(V²)dist[n][n]
경로 배열O(V²)next[n][n] (선택적)
전체O(V²)2차원 배열

⚖️ 7️⃣ 다익스트라와의 비교

💡 핵심 차이점

구분플로이드-워셜다익스트라
목적모든 쌍 최단 경로한 정점에서 모든 정점으로
시간복잡도O(V³)O((V+E)logV)
공간복잡도O(V²)O(V)
음수 간선가능 (음수 사이클 제외)불가능
구현 난이도매우 쉬움중간 (우선순위 큐)
적용 상황정점이 적을 때 (V ≤ 500)정점이 많을 때, 특정 출발점

💡 언제 무엇을 쓸까?

// ✅ 플로이드-워셜을 쓸 때
if (모든 정점 쌍의 최단 거리가 필요 && 정점 수 ≤ 500) {
    플로이드워셜();
}

// ✅ 다익스트라를 쓸 때
if (특정 출발점에서 모든 정점까지 && 음수 간선 없음) {
    다익스트라();
}

// ✅ 벨만-포드를 쓸 때
if (음수 간선 있음 && 음수 사이클 감지 필요) {
    벨만포드();
}

🎯 8️⃣ 실전 문제 적용

💡 대표 문제 유형

유형설명예시 문제
모든 쌍 최단 경로모든 도시 간 최단 거리백준 11404 플로이드
경유지 문제특정 경유지를 거쳐야 할 때프로그래머스 순위
연결성 판단모든 노드가 연결되어 있는가?백준 1389 케빈 베이컨
최단 경로 개수최단 경로가 몇 개인가?백준 1613 역사

💡 체크리스트

플로이드-워셜 문제를 풀 때 확인할 것:

  • 정점 수가 500 이하인가? (아니면 다익스트라 고려)
  • 모든 쌍의 최단 거리가 필요한가?
  • 음수 간선이 있는가?
  • 음수 사이클을 감지해야 하는가?
  • INF 값을 충분히 크게 설정했는가?
  • 중복 간선 처리를 했는가?
  • k가 가장 바깥 루프인가?