19강: 여러 출발지에서 한 번에 최단 경로, 플로이드-워셜(Floyd-Warshall) 알고리즘
AI 사용 안내: 이 포스팅은 ChatGPT(GPT-5.5 Thinking) 언어 모델을 활용하여 작성되었습니다.
19강: 여러 출발지에서 한 번에 최단 경로, 플로이드-워셜(Floyd-Warshall) 알고리즘
안녕하세요. 재준봇입니다.
지난 강의에서는 프림 알고리즘을 통해
“최소 비용으로 전체를 연결하는 방법”을 배웠습니다.
그때 핵심은 이거였습니다.
연결된 영역에서 가장 싸게 확장
그런데 이번엔 완전히 다른 질문이 나옵니다.
🎯 오늘 강의 핵심 한 줄 요약
플로이드-워셜 = 모든 노드 간 최단 거리 한 번에 구하기
1. 이 알고리즘이 왜 필요한가?
이건 언제 필요하냐면 이런 상황입니다:
- 모든 노드 간 최단 거리 필요
- 한 번 계산해서 계속 써야 하는 경우
- 그래프가 작지만 질의가 많은 경우
초보자들은 보통 이렇게 생각합니다:
“다익스트라를 N번 돌리면 되지 않나요?”
맞습니다. 틀린 말은 아닙니다.
하지만…
👉 N번 돌리는 순간 성능 터집니다
💥 실제로 터지는 이유
- 다익스트라: O(E log V)
- N번 반복 → O(N * E log V)
👉 입력 커지면 바로 시간 초과
그래서 등장한 게:
👉 플로이드-워셜
2. 오늘의 실전 문제
🎬 상황
여러분은 택시 회사 서버를 만들고 있습니다.
고객이 계속 물어봅니다:
“A에서 B까지 최단 거리 얼마야?”
이 질문이 하루에 수십만 번 들어옵니다.
📌 조건
- 도시 개수: N
- 모든 도시 간 거리 필요
- 질의 매우 많음
🎯 목표
모든 도시 쌍의 최단 거리 구하기
🧠 초보자 폭풍 질문
“다익스트라 여러 번 쓰면 되는 거 아닌가요?”
가능합니다.
하지만:
- 질의 많으면 비효율
- 매번 계산하면 서버 터짐
👉 그래서 한 번에 계산
🔥 핵심 개념
“중간 노드를 하나씩 거쳐보면서 거리 갱신”
이게 전부입니다.
🎮 직관 비유
이걸 이렇게 생각하면 됩니다:
“A → B 직접 가는 것보다
A → C → B가 더 빠른지 계속 확인”
3. 알고리즘 흐름
- 모든 거리 초기화
- 중간 노드 하나 선택
- 모든 경로 갱신
- 반복
💣 실무주의보
❗ 1. 음수 사이클
→ 있으면 결과 무의미
❗ 2. 메모리
→ N^2 사용
❗ 3. 큰 입력
→ 절대 쓰면 안됨
📊 시간 복잡도
- 시간: O(N^3)
- 공간: O(N^2)
👉 작을 때만 사용
4. 문제 다시 정리
모든 노드 간 최단 거리 계산
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드
- 거리 배열 생성
- 초기값 설정
- 3중 반복문
- 거리 갱신
파이썬 정답 코드
def floyd_warshall(n, graph):
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in graph:
dist[u][v] = w
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
graph = [
(0, 1, 4),
(0, 2, 2),
(1, 2, 5),
(2, 3, 1)
]
result = floyd_warshall(4, graph)
for row in result:
print(row)
코드 흐름
- 초기화 → 거리 세팅
- 반복 → 중간 노드 검사
- 결과 → 최단 거리
예상 출력
[0, 4, 2, 3]
[inf, 0, 5, 6]
[inf, inf, 0, 1]
[inf, inf, inf, 0]
실무 개선
- sparse graph → 다익스트라 사용
- 큰 데이터 → 절대 금지
- 캐싱 활용
5. 핵심 요약
- 모든 노드 거리 계산
- 3중 루프
- 중간 노드 활용
🎯 한 문장 정리
모든 노드 간 최단 거리 = 플로이드-워셜
6. 마무리
이제 여러분은:
- 다익스트라 (단일 시작)
- 프림 (최소 연결)
- 플로이드 (전체 거리)
이 3개를 이해했습니다.
이 정도면 그래프 기본기는 끝났습니다.
다음 강의는 진짜 더 재밌습니다.