🟣 관계를 그림으로 옮긴다
지금까지는 원소가 일렬로 늘어선 배열과 수열을 다뤘다. 그런데 현실의 많은 문제는 순서가 아니라 관계로 얽혀 있다. 도시와 도시를 잇는 도로, 사람과 사람을 잇는 친구 관계, 작업과 작업 사이의 선후 의존성이 그렇다. 이런 문제는 대상을 노드(정점)로, 관계를 간선으로 그린 그래프로 옮기는 순간 다룰 수 있게 된다.
그래프를 코드로 담는 방법은 두 가지다. 인접 행렬은 n×n 표에 두 노드가 이어졌는지를 적는다. 조회는 O(1)로 빠르지만 노드가 많고 간선이 적으면 O(n²) 공간이 낭비된다. 인접 리스트는 각 노드마다 이웃 목록을 들고, 간선 수에 비례하는 공간만 쓴다. 현실의 그래프는 대개 간선이 성글어서 인접 리스트를 기본으로 삼는다. 표현을 고르는 것부터가 그래프 문제의 첫 판단이다.
🟣 BFS와 DFS: 그래프를 훑는 두 방법
그래프에서 하는 거의 모든 일은 탐색에서 시작한다. 한 노드에서 출발해 이어진 노드를 빠짐없이 방문하는 방법이 둘 있다.
너비 우선 탐색(BFS)은 큐를 써서 가까운 노드부터 물결처럼 퍼져 나간다. 출발점에서 거리가 1인 노드를 모두 본 뒤 거리 2로 넘어간다. 이 성질 덕분에 간선 가중치가 없는 그래프에서 최단 경로를 바로 구한다. 처음 도달한 순간이 곧 최단이기 때문이다.
깊이 우선 탐색(DFS)은 스택(또는 재귀)을 써서 한 방향으로 갈 수 있는 데까지 내려갔다가 막히면 되돌아온다. 사이클을 찾거나, 연결 요소를 세거나, 위상 정렬처럼 방문 순서 자체가 의미를 갖는 문제에 쓴다.
위 그래프를 A에서 BFS로 훑으면 거리 순으로 A, 그다음 B와 C, 그다음 D와 E를 본다. DFS로 훑으면 A에서 B로 내려가 D까지 갔다가 되돌아와 C, E로 간다. 같은 그래프인데 무엇을 알고 싶은지에 따라 훑는 순서를 고른다.
🚀 위상 정렬: 순서가 있는 작업
작업들 사이에 "A가 끝나야 B를 할 수 있다" 같은 선후 관계가 있으면 방향 그래프로 그린다. 이때 모든 의존성을 어기지 않는 작업 순서를 찾는 것이 위상 정렬이다. 빌드 시스템이 소스 파일의 컴파일 순서를 정하거나, 패키지 매니저가 의존성 설치 순서를 정하는 일이 정확히 이것이다. DFS로 먼저 끝나는 노드를 역순으로 쌓거나, 들어오는 간선이 없는 노드부터 차례로 빼내면 순서가 나온다. 이 과정에서 사이클이 발견되면 순환 의존이라 순서 자체가 존재하지 않는다.
🟣 가중치가 있으면: 최단 경로
간선마다 거리나 비용 같은 가중치가 붙으면 BFS로는 부족하다. 간선 하나를 덜 지나는 경로가 오히려 더 멀 수 있기 때문이다. 가중치 그래프의 최단 경로에는 다른 도구가 필요하다.
다익스트라 알고리즘은 음수 간선이 없는 그래프에서 한 출발점부터 모든 노드까지의 최단 거리를 구한다. 아직 확정 안 된 노드 중 현재 거리가 가장 짧은 것을 우선순위 큐로 골라 확정하고, 그 노드를 거쳐 이웃까지 가는 거리가 더 짧아지면 갱신한다. 이 "가장 가까운 것부터 확정"이 그리디 선택이고, 음수 간선이 없어야 한 번 확정한 거리가 뒤집히지 않는다. 우선순위 큐를 쓰면 O(E log V)에 돈다.
음수 간선이 있으면 다익스트라의 전제가 깨진다. 이때는 벨만-포드를 쓴다. 모든 간선을 V-1번 훑으며 거리를 갱신하는 방식이라 O(VE)로 느리지만 음수 간선을 감당한다. 한 바퀴 더 돌아도 거리가 줄어들면 음수 사이클이 있다는 뜻이라, 최단 경로가 정의되지 않음까지 잡아낸다. 음수 간선의 유무가 어느 알고리즘을 쓸지 가른다.
🟣 최소 신장 트리: 가장 싸게 모두 잇기
노드를 전부 연결하되 간선 비용 합을 최소로 하고 싶을 때가 있다. 도시를 전부 잇는 최소 비용 도로망 같은 문제다. 사이클 없이 모든 노드를 잇는 부분 그래프가 신장 트리이고, 그중 비용이 최소인 것이 최소 신장 트리(MST)다. 대표 알고리즘 둘 다 그리디다.
크루스칼은 간선을 비용이 싼 순서로 보며, 사이클을 만들지 않는 간선만 골라 담는다. 프림은 한 노드에서 시작해 트리에 붙일 수 있는 가장 싼 간선으로 트리를 키운다. 둘 다 "지금 가장 싼 선택"을 반복하는 그리디인데, MST에서는 이 그리디가 최적임이 증명돼 있다. 앞 장에서 본 그리디 선택 속성이 그래프에서 다시 등장하는 셈이다.
크루스칼에는 문제가 하나 있다. 간선을 담을 때마다 이 간선이 사이클을 만드는지, 즉 두 노드가 이미 같은 덩어리에 속하는지 빠르게 판별해야 한다. 이걸 소박하게 탐색으로 확인하면 느려진다. 여기서 union-find가 등장한다.
🚀 유니온 파인드: 같은 덩어리인지 빠르게 묻기
유니온 파인드(합집합 찾기)는 원소들이 어느 집합에 속하는지 관리하는 자료구조다. 연산은 둘뿐이다. 두 원소가 같은 집합인지 대표를 찾아 확인하고(find), 두 집합을 하나로 합친다(union). 각 집합을 트리로 표현하고 뿌리를 대표로 삼는다.
그냥 쓰면 트리가 한쪽으로 길어져 find가 느려진다. 두 가지 최적화가 이걸 막는다. 경로 압축은 find를 하면서 지나온 노드를 뿌리에 직접 붙여 다음 조회를 빠르게 한다. 랭크 기반 합침은 항상 낮은 트리를 높은 트리 밑에 붙여 높이가 늘지 않게 한다. 둘을 함께 쓰면 연산 하나가 사실상 상수 시간에 가까워진다. 정확히는 아커만 함수의 역함수가 붙는데, 현실의 어떤 입력에서도 4를 넘지 않아 상수로 봐도 된다. 크루스칼의 사이클 판별이 이 덕분에 빨라진다.
🟣 정리
- 관계로 얽힌 문제는 노드와 간선의 그래프로 옮기면 다룰 수 있다. 인접 행렬과 인접 리스트 중 성긴 그래프에는 리스트를 쓴다.
- BFS는 가까운 곳부터 퍼져 가중치 없는 최단 경로를 주고, DFS는 깊이 내려가며 사이클 탐지와 위상 정렬에 쓴다.
- 가중치 최단 경로는 음수 간선이 없으면 다익스트라, 있으면 벨만-포드다. 음수 간선의 유무가 선택을 가른다.
- 최소 신장 트리는 크루스칼과 프림 모두 그리디로 푼다. 그래프에서도 그리디 선택 속성이 최적을 보장한다.
- 유니온 파인드는 경로 압축과 랭크 합침으로 집합 판별을 사실상 상수 시간에 처리한다. 크루스칼의 사이클 판별이 이 위에 선다.
그래프는 실무에 가장 넓게 닿는 주제다. 지도 길찾기, 소셜 그래프의 친구 추천, 빌드 의존성 해석, 마이크로서비스 호출 관계 분석이 전부 이 장의 알고리즘이다. 면접에서도 BFS/DFS 구현과 최단 경로는 반드시 나온다. 여기까지는 모두 다항 시간에 효율적으로 풀렸다. 마지막 장은 그 전제가 깨지는 세계, 아무리 잘 설계해도 빠르게 풀 수 없는 문제들이다.