그래프 알고리즘 투어 — DFS부터 최단 경로까지 9종
노드 6개 지도 하나 위에서 DFS·BFS·사이클·이분·DSU·위상·Flood Fill·MST·다익스트라를 실제 실행하고, 각 알고리즘이 '어떤 질문에 답하는가'를 사례와 함께 붙인다.
1 / 11노드 6개짜리 지도 하나로 그래프 알고리즘 아홉을 순례합니다. 각 알고리즘은 '무엇을 묻는 질문인가'가 다릅니다.
DFSBFS사이클 감지이분 판별DSU위상 정렬Flood FillMST최단 경로
단계 목록 · 키보드 ←/→ 이동, Space 재생
그래프 알고리즘은 '질문'으로 분류하면 한 번에 정리된다 — 끝까지(DFS), 몇 다리(BFS), 고리 있나(사이클), 두 편 나뉘나(이분), 같은 무리인가(DSU), 순서는(위상), 어디까지 번지나(Fill), 전부 잇는 최소 비용(MST), 가장 싼 길(최단).
왜 헷갈리는가
MST와 최단 경로가 대표 혼동 짝이다 — 둘 다 '싼 간선'을 고르지만 MST는 '모든 노드 연결'의 최소 비용이고 최단 경로는 '한 쌍 사이 길'의 최소 비용이다. MST 위의 두 노드 경로가 최단이 아닐 수 있다. DFS/BFS도 마찬가지: 최단 홉이 필요한 순간 DFS는 오답이 된다.
아홉 질문과 실생활
각 알고리즘의 자리.
- DFS: 미로 완주, 사이클·위상의 기반, 연결 요소 — '끝까지 가 봐야 아는' 질문. 스택/재귀.
- BFS: 친구의 친구(몇 다리), 무가중 최단, 웹 크롤링 레벨 — 큐가 물결을 지킨다.
- 사이클 감지: 교착(자원 대기 그래프), 패키지 순환 의존 — '이 의존성 추가해도 되나'.
- 이분 판별: 지원자-일자리 매칭, 두 진영 배정 — 홀수 고리가 있으면 불가능.
- DSU: 크루스칼의 심장, 네트워크 연결성, 실시간 무리 판정 — 경로는 못 주고 소속만 준다(거의 O(1)).
- 위상 정렬: 빌드 순서, 수강 계획, 작업 의존 — DAG 전용, 사이클이 있으면 순서가 모순.
- Flood Fill: 그림판 페인트통, 지뢰찾기 빈칸, 섬 개수 — 격자 위의 DFS/BFS.
- MST(크루스칼/프림): 전력망·통신망 부설, 클러스터링 — '전부 연결'이 목적.
- 다익스트라: 내비게이션, 라우팅 — '한 쌍의 최단'. 음수 간선은 벨만-포드로.
고르기의 첫 질문
"가중치가 있는가, 방향이 있는가, 무엇이 답인가(순서·경로·집합·판정)" — 세 질문이면 아홉 중 하나로 수렴한다. 무가중 최단은 BFS로 충분하다는 것(다익스트라 불필요), DSU는 union의 역연산이 없다는 것(끊기는 못 다룸)이 자주 놓치는 디테일이다.
기억할 것
- 알고리즘이 아니라 질문을 외워라 — 질문이 답을 고른다.
- MST ≠ 최단 경로: 전부 연결의 최소 vs 한 쌍의 최소.
- 무가중 최단은 BFS면 충분 — 다익스트라는 가중치용.
- 사이클은 순서(위상)의, 홀수 고리는 2색(이분)의 훼방꾼.