플로이드-와샬 알고리즘 (Floyd-Warshall)

모든 정점 간의 최단 경로를 계산해야 하는 문제를 풀 때 자주 사용되는 방법이 무엇일까요?

그건 바로 플로이드 워샬, 플로이드 워셜, 플로이드 와셜 등 여러 이름으로 불리는 플로이드-와샬 알고리즘입니다!

이번 포스팅에서 플로이드 와샬 알고리즘에 대해 학습하고 문제까지 풀어봤습니다 😊

---

1. 플로이드-와샬 알고리즘 (Floyd-Warshall)

그래프에서 모든 정점 간의 최단 경로를 계산하는 알고리즘
-> 방향 그래프, 무방향 그래프 모두 사용 가능
-> 음수 가중치는 상관 없음, 하지만 음수 사이클에서는 사용 불가

• 모든 노드 쌍의 최단 경로를 한 번에 계산 가능 (배열에 저장하니까)

• 동적 계획법(DP) 기반 알고리즘
  -> 노드 간의 거리 중 가장 작은 것들을 조합해 최종적으로 최단 거리 반환하기 때문

음수 사이클

그래프의 특정 순환 경로 가중치 합이 음수가 되는 사이클
⠀
ex) A -> B -> C -> A라는 순환 경로의 가중치 합이 -5라면 음수 사이클임
=> 이 사이클을 반복할 수록 최단거리 갱신됨 (-Infinity로 향해가니까)
=> 이런 경우 최단 경로를 정의할 수 없음

• 구현 방식

  1. 그래프의 각 가중치를 저장하는 2차원 배열 생성
     -> dist[i][j]는 i -> j의 거리(가중치)
     -> 연결되지 않은 노드들은 Infinity, 자기 자신은 0 할당

  2. 모든 노드들이 중간 노드가 될 수 있도록 k로 for문을 돌고, 이때 i -> j와 i -> k -> j의 거리를 비교해 최단거리 갱신
     -> dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

  3. dist는 모든 가능한 최단 거리 경로를 담은 배열이 됨

     => for문을 3번 돌기 때문에 시간복잡도는 O(n^3)
     -> 노드 수(n)가 많으면 계산량이 많아져서 비효율적

• 플로이드-와샬 알고리즘이 자주 사용되는 문제 유형
  • 도시 간의 최소 이동 비용 계산
  • 네트워크 지연 시간 계산
  • 모든 노드 간의 경로 길이를 구해야 하는 문제

1-2. 플로이드-와샬 알고리즘과 최소 신장 트리(MST)의 차이

문제들을 풀다보니 두 유형이 헷갈릴 수 있겠다고 느껴져 차이점을 정리했습니다.
제가 느끼기에는 모든 노드의 연결이 필수냐 아니냐에 따라 문제 유형이 달라지는 것 같습니다 !

	플로이드-와샬	MST
목적	모든 정점 간의 최단 경로 계산	모든 정점을 최소 비용으로 연결하는 트리
결과	노드 쌍 간의 최단 거리 테이블	최소 비용으로 구성된 간선들 집합
키워드	최단 거리, 모든 노드 쌍	최소 비용 연결, 스패닝 트리
그래프	방향 / 무방향 둘 다 가능	일반적으로 무방향 연결 그래프
기반 알고리즘	동적 계획법	그리디

⠀

---

2. 플로이드-와샬 관련 문제 추천 및 풀이

문제 리스트

• 백준: 11404, 2458, 1389
• 프로그래머스: 순위, 등산 코스 정하기

🔍 11404번: 플로이드

📖 풀이 코드

import sys

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
graph = [[float("inf")] * n for _ in range(n)]
for _ in range(m):
    a, b, cost = list(map(int, sys.stdin.readline().strip().split()))
    graph[a - 1][b - 1] = min(graph[a - 1][b - 1], cost)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j: continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in graph:
    curStr = " ".join(map(str, i))
    print(curStr.replace("inf", "0"))

📢 풀이 설명
이 문제는 버스의 구간이 같아도 출발, 도착 방향이 반대면 다른 노선이다. 또, 같은 노선이라도 값이 여러 개 있을 수 있다.
즉, 방향그래프이고, 같은 구간이라도 주어지는 입력의 최솟값으로 갱신해야한다.

이 점을 유의해서 풀면 플로이드-와샬 알고리즘의 정석 문제이다.

마지막으로 연결되지 않은 구간끼리의 값을 inf가 아닌 0으로 표기해야한다 !!
(문제를 꼼꼼히 읽지 않아 틀린 이유 찾느라 오래걸린 사람의 마지막 말입니다 ㅜㅜ)

---

🔍 2458번: 키 순서

📖 풀이 코드

# BFS 풀이
import sys
from collections import deque

n, m = list(map(int, sys.stdin.readline().strip().split()))
bigGraph = [[] for _ in range(n)]
smallGraph = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, sys.stdin.readline().strip().split()))
    bigGraph[a - 1].append(b - 1)
    smallGraph[b - 1].append(a - 1)
    
def bfs(i, graph):
    queue = deque([i])
    visited = [False] * n
    visited[i] = True
    count = 0

    while queue:
        num = queue.popleft()

        for k in graph[num]:
            if not visited[k]:
                visited[k] = True
                queue.append(k)
                count += 1
    return count

result = 0

for i in range(n):
    big = bfs(i, bigGraph)
    small = bfs(i, smallGraph)

    if big + small == n - 1: result += 1

print(result)


# 플로이드-와샬 풀이
import sys

n, m = list(map(int, sys.stdin.readline().strip().split()))
edges = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, sys.stdin.readline().strip().split()))
    edges[a - 1][b - 1] = 1

for k in range(n):
    for i in range(n - 1):
        for j in range(i + 1, n):
            if edges[i][k] + edges[k][j] == 2: edges[i][j] = 1

count = 0
for i in range(n):
    tmpCount = 0
    for j in range(n):
        tmpCount += edges[i][j] + edges[j][i]
    if tmpCount == (n - 1): count += 1

print(count)

📢 풀이 설명
이 문제는 Python3에서 플로이드-와샬로 풀면 시간초과가 난다. n이 최대 500이기 때문에 500^3 = 125,000,000이 되기 때문이다.
플로이드-와샬로 통과하고싶다면 PyPy를 써야한다고 한다.

파이썬3로 풀려면 dfs / bfs를 써야한다.

---

🔍 1389번: 케빈 베이컨의 6단계 법칙

📖 풀이 코드

import sys

n, m = list(map(int, sys.stdin.readline().strip().split()))
graph = [[float("inf")] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    graph[i][i] = 0
for _ in range(m):
    a, b = list(map(int, sys.stdin.readline().strip().split()))
    graph[a][b] = 1
    graph[b][a] = 1

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            graph[j][i] = graph[i][j]

result = [0, float("inf")]
for i in range(1, n + 1):
    curSum = sum(graph[i][1:])
    if curSum < result[1]: result = [i, curSum]

print(result[0])

📢 풀이 설명
직접적인 간선 간의 가중치를 그래프로 만들고, 3중 포문을 돌며 간접적 간선들의 가중치를 최솟값으로 갱신한다.
번호가 1번부터 시작되기 때문에 0번 인덱스는 inf 그대로 두었다.

이 문제는 전에 bfs로 풀었었는데 이번에는 플로이드-와샬 알고리즘으로 풀어봤다.
개인적으로는 bfs로 푸는 게 더 효율적인 것 같다.

---

🔍 순위

📖 풀이 코드

function solution(n, results) {
    let result = 0;
    const graph = Array.from({length: n + 1}, () => new Array(n + 1).fill(0));
    ⠀
    for (const [win, lose] of results) {
        graph[win][lose] = 1;
    }
    ⠀
    for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                if (graph[i][k] && graph[k][j]) graph[i][j] = 1;
            }
        }
    }
    ⠀
    for (let i = 1; i <= n; i++) {
        let count = 0;
    ⠀
        for (let j = 1; j <= n; j++) {
            count += graph[i][j] + graph[j][i];
        }
    ⠀
        if (count == n - 1) result += 1;
    }
    ⠀
    return result;
  }

📢 풀이 설명

• 2차원 배열 graph의 인덱스 번호 = 이긴 선수, 인덱스 속의 인덱스 = 진 선수
  -> 전부 0으로 초기화
  -> results 돌면서 이긴 관계는 1로 바꿈
• 플로이드-워샬 알고리즘을 이용해 k = 중간에 거치는 선수, i = 이긴 선수, j = 진 선수로 for문 3번 돌기
  -> i가 k를 이기고 && k가 j를 이기면 i가 j를 이긴 것과 같으므오 graph[i][j]도 1로 변경
• 각 선수들간의 승패 관계를 살피기 위해 i, j for문 돌기
  -> i가 j를 이겼거나 j가 i를 이겼다면 이긴 관계는 값이 1임 (둘 중 1개가 1이라면 승패가 났다는 뜻)
  -> 각 선수들과 모두 승패가 났다면 result += 1
• 최종적으로 result 반환

---

🔍 등산 코스 정하기

📖 풀이 코드

📢 풀이 설명