Algorithm

최단 경로와 최소 신장 트리

다익스트라, 벨만-포드, 플로이드-워셜로 최단 경로를 구하고 크루스칼과 프림으로 최소 신장 트리를 만드는 방법을 정리합니다.

최단 경로 문제는 가중치 그래프에서 한 정점에서 다른 정점으로 가는 경로 중 가중치 합이 가장 작은 경로를 찾는 문제입니다. 최소 신장 트리(MST)는 무방향 그래프의 모든 정점을 사이클 없이 잇는 간선 집합 가운데 가중치 합이 가장 작은 것을 찾는 문제입니다. 다익스트라, 벨만-포드, 플로이드-워셜, 0-1 BFS, 크루스칼, 프림이 이 주제의 핵심 알고리즘입니다.

지도 길찾기, 네트워크 라우팅(OSPF, RIP), 게임의 경로 찾기, 배선과 배관 설계, 군집화처럼 실제 시스템 곳곳에서 이 알고리즘들이 돌아갑니다. 코딩 테스트와 기술 면접에도 자주 나오는데, 문제를 그래프로 모델링하고 가중치의 성질(음수가 있는지, 0과 1뿐인지, 그래프가 얼마나 밀집했는지)에 맞는 알고리즘을 고르는 능력을 보기 좋기 때문입니다.

먼저 BFS와 우선순위 큐(힙)에 익숙해진 뒤, 모든 알고리즘의 공통 연산인 완화(relaxation)를 이해하고 작은 그래프에서 다익스트라를 손으로 따라가 보는 것이 좋습니다. 이어서 음수 간선이 있을 때 벨만-포드가 필요한 이유를 확인하고, 유니온 파인드를 쓰는 크루스칼을 직접 구현해 봅니다. 마지막으로 상태를 넓혀 다익스트라를 돌리는 연습 문제로 응용력을 기릅니다.