Algorithm

[Algorithm] 플로이드–워셜 알고리즘(Floyd-Warshall) 완벽 정리 - 그래프 모든 경로 탐색

Rubi ❤️ 2025. 5. 11. 02:21
728x90
반응형

🚀 플로이드–워셜 알고리즘(Floyd-Warshall) 완벽 정리

그래프 모든 경로와 최단 거리 탐색을 한 번에!

📌 개념

플로이드–워셜(Floyd–Warshall) 알고리즘은
그래프 이론에서 모든 정점 쌍 간의 최단 경로를 효율적으로 구하는 알고리즘입니다.

  • ✅ 모든 정점 → 모든 정점 거리 계산 가능
  • ✅ 음수 간선 허용 (단, 음수 사이클은 안 됨)
  • ✅ 거리뿐 아니라 도달 가능 여부도 계산 가능

예: A에서 B로 직접 경로가 없더라도, A → C → B로 우회할 수 있다면 경로로 인식함.

🧠 동작 방식 (점화식 기반)

플로이드–워셜의 핵심은 다음과 같은 점화식입니다:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  • i: 출발 노드
  • j: 도착 노드
  • k: 경유지 노드 (중간에 거쳐 가는 노드)

즉, i → j로 가는 경로가 i → k → j로 우회하면 더 짧을 수 있는지 확인합니다. 

이를 통해 해당 경로로 가는 최단 거리를 계산할 수 있습니다. 

🔄 알고리즘 흐름

  1. 초기화
    • dist[i][j] = 간선 가중치 (간선이 없다면 INF)
    • dist[i][i] = 0
  2. 3중 루프 실행
for (int k = 0; k < N; ++k) 
	for (int i = 0; i < N; ++i) 
    	for (int j = 0; j < N; ++j) 
        	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

 

 3. 모든 정점 쌍의 최단 거리/도달 가능 여부 갱신 완료

📋 예제: 도달 가능 여부 구하기 (백준 11403번 - 경로 찾기)

🔸 입력 인접 행렬

3
0 1 0
0 0 1
1 0 0
  • 0 → 1
  • 1 → 2
  • 2 → 0
    → 모든 노드를 순환하며 도달 가능

🔸 기대 출력

1 1 1
1 1 1
1 1 1

💻 C++ 코드 (도달 가능 여부)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> graph(N, vector<int>(N));
    
    // 입력 받기
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> graph[i][j];

    // 플로이드-워셜 실행
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (graph[i][k] && graph[k][j])
                    graph[i][j] = 1;

    // 결과 출력
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            cout << graph[i][j] << " ";
        cout << "\n";
    }
}

🧪 적용 예시

1️⃣ 최단 거리 구하기

  • dist[i][j]에 실제 가중치를 저장
  • dist[i][j] = INF로 초기화한 뒤 min()을 통해 갱신

2️⃣ 경로 존재 여부 확인

  • graph[i][j]를 0 또는 1로 두고
    graph[i][j] = 1로 갱신

3️⃣ 자기 자신으로 돌아오는 경로 탐지

  • graph[i][i] == 1이면
    i에서 출발해 다시 i로 돌아오는 사이클 존재

📈 시간 복잡도

항목 값
시간 복잡도 O(N³)
공간 복잡도 O(N²)
추천 최대 정점 수 N ≤ 400 (Python), N ≤ 500~1000 (C++)

✅ 요약 정리

기능 가능 여부
모든 정점 간 최단 거리 계산 ✅
도달 가능 여부 판단 ✅
음수 가중치 허용 ✅
음수 사이클 ❌ 불가능
경로 복원 ✅ 가능 (별도 배열 필요)

📝 마무리

플로이드–워셜 알고리즘은
"하나씩 다 가봐야 할 것 같은 모든 경로 문제"를 단 하나의 알고리즘으로 해결해줍니다.
특히 도달 가능 여부, 사이클 탐지, 전이 행렬 계산에 매우 유용합니다! 

 

💡 도움이 되셨다면 댓글이나 공감 부탁드려요!
궁금한 점은 언제든지 남겨주시면 답변 드립니다. 😊

 

728x90
반응형