8강: 모든 길은 통한다, 플로이드-워셜(Floyd-Warshall) 알고리즘

5 minute read

8강: 모든 길은 통한다, 플로이드-워셜(Floyd-Warshall) 알고리즘

반가워요! 코딩하는 세상의 힙스터, 재준봇입니다!

지난 7강에서는 흩어진 내 편을 하나로 묶어주는 유니온 파인드(Union-Find)에 대해 알아봤죠? 서로가 같은 팀인지 확인하고 합치는 그 쾌감, 다들 기억하시나요? 유니온 파인드가 관계의 연결고리를 찾는 작업이었다면, 오늘 배울 내용은 그 연결고리를 이용해 세상의 모든 최단 거리를 싹 다 긁어모으는 아주 욕심 많은 알고리즘입니다.

자, 오늘 우리가 정복할 녀석은 바로 플로이드-워셜(Floyd-Warshall) 알고리즘입니다. 이름부터가 뭔가 있어 보이죠? 하지만 겁먹지 마세요. 재준봇이 아주 찰떡같은 비유로 뇌에 때려 박아 드릴게요.

1. 플로이드-워셜, 도대체 왜 쓰는 건가요?

우리가 예전에 배웠던 다익스트라 알고리즘 기억하시죠? 다익스트라는 한 지점에서 다른 모든 지점까지 가는 최단 거리를 구하는 녀석입니다. 즉, 출발지가 정해져 있는 일방적인 사랑 같은 거죠.

그런데 세상에는 이런 상황이 있습니다. “나 그냥 여기서 저기까지 가는 거 말고, 이 도시들 사이에 있는 모든 경로의 최단 거리를 한 번에 표로 만들어 놓고 싶어!”라는 상황 말입니다. 이때 다익스트라를 쓰려면 모든 정점에서 각각 다익스트라를 돌려야 하는데, 이건 너무 비효율적이에요.

이때 구원투수로 등장하는 것이 바로 플로이드-워셜입니다. 이 알고리즘의 핵심은 이거예요.

“A에서 B로 바로 가는 것보다, 중간에 K라는 지점을 거쳐서 가는 게 더 빠를까?”

이 질문을 모든 정점에 대해 계속 던지는 겁니다. 마치 우리가 맛집을 찾을 때, 집에서 식당으로 바로 가는 길보다 중간에 친구네 집을 들렀다 가는 길이 결과적으로 더 빠르거나 효율적일 때가 있는 것과 비슷하죠.

2. 찰떡 비유: 전 우주 최단 거리 배송 지도 만들기

여러분이 은하계 택배 회사의 사장님이라고 상상해 보세요. 우주에는 여러 행성이 있고, 행성 사이에는 웜홀이 연결되어 있습니다. 그런데 고객들이 매번 “A행성에서 B행성까지 얼마나 걸려요?”라고 물어봅니다.

매번 계산하기 귀찮은 사장님은 아예 모든 행성 간의 최단 거리가 적힌 거대한 표(2차원 배열)를 만들기로 했습니다.

처음에는 알고 있는 웜홀 거리만 적어둡니다. 그러다가 문득 깨닫죠. “어? A에서 B로 바로 가는 웜홀은 100광년인데, A에서 C행성을 거쳐 B로 가면 10광년 + 20광년 해서 30광년밖에 안 되네?”

이렇게 중간 기착지(K)를 하나씩 추가하며 표의 값을 계속 업데이트하는 것이 플로이드-워셜의 전부입니다. 진짜 신기하죠?

3. 이 알고리즘의 정체 (시간 복잡도와 특징)

여기서 주의할 점이 있습니다. 이 알고리즘은 매우 강력하지만, 그만큼 대가가 따릅니다.

시간 복잡도: O(V^3)
V는 정점(Vertex)의 개수입니다. 정점이 100개라면 100의 3제곱, 즉 1,000,000번의 연산을 합니다.
하지만 정점이 1,000개만 되어도 10억 번의 연산을 해야 합니다.

즉, 데이터가 너무 많으면 컴퓨터가 비명을 지르며 멈출 수 있습니다. 그래서 이 알고리즘은 보통 정점의 개수가 적을 때(보통 500개 이하) 사용합니다. 이거 모르면 코딩 테스트에서 시간 초과로 광탈할 수 있으니 정말 주의해야 합니다!

초보자 폭풍 질문! Q: 재준봇님! 그럼 그냥 다익스트라를 여러 번 돌리는 게 더 빠른 거 아닌가요?

A: 오, 날카로운 질문입니다! 정점의 개수가 많고 간선(길)의 개수가 적을 때는 다익스트라를 여러 번 돌리는 게 더 빠를 수 있습니다. 하지만 구현이 훨씬 간단하고, 모든 경로를 한 번에 관리할 수 있다는 점에서 플로이드-워셜은 매우 매력적이죠. 특히 음수 가중치(길을 지나가면 오히려 돈을 주는 경우)가 있을 때 다익스트라는 못 쓰지만, 플로이드-워셜은 (음수 사이클만 없다면) 사용할 수 있다는 엄청난 장점이 있습니다!

4. 실무주의보: 여기서 실수하면 끝장납니다!

실무나 코딩 테스트에서 플로이드-워셜을 쓸 때 가장 많이 하는 실수가 있습니다. 바로 초기값 설정입니다.

연결되지 않은 경로를 0으로 설정하면 안 됩니다. 왜냐하면 알고리즘이 min(현재 거리, 거쳐가는 거리)를 계산하는데, 0이 있으면 무조건 0이 최단 거리라고 판단해 버리거든요. 그래서 연결되지 않은 경로는 아주 큰 값(INF, 무한대)으로 설정해야 합니다. 보통 1e9(10억) 같은 값을 사용하죠.

🚀 오늘의 도전 문제: [은하계 최단 거리 물류망 설계]

상황 제시: 당신은 은하계 물류 센터의 수석 엔지니어입니다. 현재 우주에는 N개의 행성이 있고, 일부 행성들 사이에는 양방향 웜홀이 설치되어 있습니다. 각 웜홀을 통과하는 데 걸리는 시간이 다릅니다.

당신은 모든 행성 쌍 간의 최단 이동 시간을 계산하여 ‘우주 물류 지도’를 완성해야 합니다. 만약 어떤 행성에서 다른 행성으로 갈 수 있는 방법이 전혀 없다면, 그 값은 무한대(INF)로 표시하세요.

입력 조건:

행성의 개수 N (2 <= N <= 100)
웜홀의 개수 M
각 웜홀의 시작 행성, 끝 행성, 소요 시간

요구사항: 모든 행성 간의 최단 거리를 구하는 2차원 배열을 출력하세요.

해결 방안 및 정답 코드 보기 (클릭)

해결 방안 가이드 (알고리즘 설계)

이 문제는 전형적인 ‘모든 쌍 최단 경로’ 문제이므로 플로이드-워셜 알고리즘을 적용합니다.

거리 행렬 초기화:
- N x N 크기의 2차원 배열을 만듭니다.
- 자기 자신으로 가는 거리(dist[i][i])는 0으로 설정합니다.
- 나머지는 모두 아주 큰 값(INF)으로 채웁니다.
간선 정보 입력:
- 주어진 웜홀 정보를 바탕으로 dist[start][end]와 dist[end][start]에 소요 시간을 저장합니다. (양방향이므로 둘 다 저장!)
3중 반복문 실행 (핵심 로직):
- 가장 바깥쪽 루프 (k): 거쳐갈 중간 지점을 정합니다.
- 중간 루프 (i): 출발 지점을 정합니다.
- 가장 안쪽 루프 (j): 도착 지점을 정합니다.
- 업데이트 식: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- 즉, “i에서 j로 바로 가는 것보다, k를 거쳐서 가는 게 더 빠른가?”를 체크하여 더 작은 값으로 갱신합니다.

파이썬 정답 코드 및 상세 해설

import sys

def solve():
    # INF 값 설정 (충분히 큰 값으로 설정하여 경로 없음으로 처리)
    INF = int(1e9)
    
    # 입력 예시: 행성 수 N, 웜홀 수 M
    # 실제 환경에서는 input() 혹은 sys.stdin.readline() 사용
    n, m = map(int, input().split())
    
    # 1. 거리 행렬 초기화
    # 모든 거리를 무한대로 설정하고, 자기 자신으로 가는 거리는 0으로 설정
    dist = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dist[i][i] = 0
        
    # 2. 웜홀 정보 입력
    for _ in range(m):
        u, v, w = map(int, input().split())
        # 양방향 통행이 가능하므로 양쪽에 모두 저장
        # 만약 중복 경로가 있을 수 있다면 min(dist[u][v], w) 처리가 필요함
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
            
    # 3. 플로이드-워셜 알고리즘 핵심 로직
    # k = 거쳐가는 노드, i = 출발 노드, j = 도착 노드
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                # i에서 j로 바로 가는 것보다 k를 거쳐가는 것이 더 빠르면 갱신
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    # 4. 결과 출력
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if dist[i][j] == INF:
                print("INF", end=" ")
            else:
                print(dist[i][j], end=" ")
        print()

# 실행 부분
if __name__ == "__main__":
    solve()

코드 포인트 설명

3중 for문의 순서: 반드시 k(거쳐가는 노드)가 가장 바깥쪽 루프여야 합니다. i나 j가 먼저 나오면 최단 거리가 제대로 갱신되지 않는 치명적인 오류가 발생합니다.
시간 복잡도: $O(N^3)$입니다. 행성이 100개라면 $100^3 = 1,000,000$번 연산하므로 충분히 가능하지만, 행성이 1,000개라면 $1,000,000,000$번 연산이 되어 시간 초과가 날 확률이 매우 높습니다.
INF 처리: 연결되지 않은 경로를 출력할 때는 무한대 값(INF)을 그대로 출력하기보다 문제 요구사항에 맞춰 "INF" 혹은 특정 문구로 처리해줘야 합니다.

요약

플로이드-워셜은 모든 지점에서 모든 지점으로의 최단 거리를 구할 때 사용한다.
3중 for문을 사용하며, 거쳐가는 노드(k)가 가장 위에 와야 한다.
시간 복잡도가 $O(N^3)$이므로, 데이터의 개수(N)가 적을 때(보통 500개 이하)만 사용 가능하다.

<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Twitter Facebook LinkedIn