목차
- 들어가며
- 신장 트리(Spanning Tree)란?
- 크루스칼(Kruskal) 알고리즘
- 마치며
1. 들어가며
며칠 전, 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 문제를 접했다. 가중치가 있는 그래프를 구축할 때, 최소한의 연결로 전체 가중치 합의 최소를 구했어야 했다.
'최소 비용'이라는 키워드에 반사적으로 다익스트라(Dijkstra) 알고리즘을 떠올렸다. 그러나 이내 두 문제에서 요구하는 최적화의 대상이 다름을 깨달았다.
다익스트라의 관심사는 시작 정점으로부터 모든 정점까지의 최소 가중치인 반면, 문제의 관심사는 그래프를 구축했을 때 가중치의 합이 최소가 되는 것이었다.
실제로 위 그림에서 모든 노드를 잇는 전체 최소 비용은 10이다. 하지만 1번 정점에서 다익스트라를 시작하면, 2번 정점을 방문하기 위해 가장 저렴한 비용인 7짜리 간선을 선택해버리는 문제가 발생한다. 매 순간 최소 비용을 선택한 것이 전체의 최소비용을 보장하지 못한다는 것이다.
1번 정점 관점에서는 저렴한 경로이지만, 전체 그래프 관점에서는 불필요한 경로를 따른 셈이다.
따라서 이 문제를 효율적으로 해결하기 위해서는 신장 트리(Spanning Tree)에 대한 개념과 크루스칼(Kruskal) 알고리즘에 대해서 알아야 한다.
2. 신장 트리(Spanning Tree)란?
조건
신장 트리에 대해서 정의 내리기 전에, 신장 트리가 될 수 있는 조건을 먼저 확인해보면 다음과 같다.
- 모든 노드가 포함되어야 한다.
- 사이클이 없어야 한다.
- 간선의 갯수가 정점의 갯수 - 1개로, 최소한의 간선만 존재해야한다.
정의
즉, 신장트리에 대해서 다음과 같이 정의할 수 있다.
최소한의 간선으로 모든 노드가 이어진, 사이클이 없는 그래프
최소 신장 트리(Minimum Spanning Tree, MST)
신장 트리에 대해서 이해했다면 가중치의 합이 최소인 신장트리가 곧 최소 신장 트리임을 쉽게 이해할 수 있다.
3. 크루스칼(Kruskal) 알고리즘
동작 원리
크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘이며, 그리디(Greedy) 알고리즘이 핵심적으로 작용한다. 알고리즘 동작 순서는 다음과 같다.
- 가중치 기준, 간선 오름차순 정렬
- 사이클 검사
- 트리 추가
예제로 살펴보기
다음과 같은 그래프가 있다고 가정해보자. (v는 정점을, w는 가중치를 의미한다.)
해당 그래프를 크루스칼 알고리즘을 통해 최소 신장 트리로 바꿔보자.
1. 가중치 기준, 간선 오름차순 정렬
전체 가중치의 합이 최소가 되어야 하기에, 가중치를 기준으로 간선을 오름차순 정렬해줘야 한다.
한 정점에서 다른 정점까지의 간선이 여러개 있다고 해도, 신장 트리의 조건인 간선의 갯수는 정점의 갯수 - 1개(최소성)에 의해 결국 간선은 1개만 남는다.
따라서 먼저 선택된 간선이 곧 유일한 간선이며, 뒤의 간선 연결에 영향을 주지 않음으로 그리디를 적용할 수 있는 것이다.
2. 사이클 검사
간선 정렬을 마친 후, 이제 가중치가 낮은 간선을 하나씩 택하며 연결해주면 된다.
이때, 신장 트리에는 사이클이 없어야 함으로, 사이클 검사가 필수적이다. 검사는 정점의 부모를 기록해둠으로써 효율적으로 할 수 있다.
[초기화]
처음에는 어느 정점과도 연결이 안되어 있기에, 자신을 부모로 초기화 해둔다.
트리 그룹 식별이란?
한 정점에서 다른 정점으로 퍼져나가는 형태가 아닌, 간선을 기준으로 그래프를 이어주는 것이라, 간선을 연결하는 과정에서 파편화된 트리들이 생성된다. 따라서 트리들을 구별하기 위해 부모를 활용한다.
[부모 비교]
가장 가중치가 낮은 간선을 선택하여 정점 간 부모를 비교해준다.
- 부모가 다를 경우: 사이클이 성립하지 않은 것임으로, 정점 사이에 부모 관계를 맺음으로써 트리 그룹 식별을 가능하게 한다.
- 부모가 같을 경우: 사이클이 성립함으로, 해당 간선은 연결하지 않고 건너 뛴다.
3. 트리 추가
정점 3과 4의 부모가 다르기에, 사이클이 성립하지 않는다고 보고 정점 4의 부모를 정점 3으로 설정해주었다. (부모는 일관성 있게 v와 v2 중 v로 설정했다.)
이 판단 방식(부모 비교 → 다르면 연결, 같으면 스킵)을 남은 간선에 그대로 반복하면 아래와 같이 트리가 완성된다.
[정점 4와 5] 두 정점의 부모가 서로 달라 사이클이 생기지 않는다. 정점 5의 부모를 정점 4의 부모(정점 3)로 갱신하며 연결한다.
[정점 2와 4] 마찬가지로 부모가 다르므로 연결한다. 이제 정점 2, 3, 4, 5가 하나의 트리로 묶인다.
[정점 1과 5] 아직 트리에 속하지 않은 마지막 정점 1을 연결한다. 부모가 다르므로 연결이 성립한다.
[최종 완성된 최소 신장 트리]
이후 간선부터는 부모가 겹치므로 사이클이 형성된다. 따라서 최소 신장 트리는 다음과 같이 구성된다.
구현 코드
// edgeInfos[][0]: v
// edgeInfos[][1]: v2
// edgeInfos[][2]: cost
private static int kruskal(int vertexCnt, int[][] edgeInfos) {
// 비용 오름차순 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>((v, v2) -> {
return Integer.compare(v[2], v2[2]);
});
// 가중치 합
int costSum = 0;
// 부모 기록
int[] parent = new int[vertexCnt + 1];
for (int i = 1; i <= vertexCnt; i++) parent[i] = i;
while (!pq.isEmpty()) {
int[] edgeInfo = pq.poll();
int v = edgeInfo[0];
int v2 = edgeInfo[1];
int cost = edgeInfo[2];
int v1Parent = findParent(v, parent);
int v2Parent = findParent(v2, parent);
// 두 정점의 부모가 같다면 사이클이 성립함으로, 간선 연결 건너 뛰기
if (v1Parent == v2Parent)
continue;
// v2의 부모를 v1 부모로 업데이트 -> 정점 간 하나의 트리로 구축
parent[v2Parent] = v1Parent;
// 가중치 합 업데이트
costSum += cost;
}
return costSum;
}
private static int findParent(int v, int[] parent) {
// 부모 탐색 완료, 부모 반환
if (v == parent[v])
return v;
// 계속 부모 탐색
return parent[v] = findParent(parent[v], parent);
}시간 복잡도
크루스칼 알고리즘의 시간 복잡도는 간선들을 정렬하는 연산에 의해 가장 큰 영향을 받으며 최종적으로 O(E log E) (E: 간선의 개수)이다.
알고리즘 내부에서 사이클 검사를 위해 사용하는 부모를 찾는 연산(Union-Find)은 경로 압축을 통해 사실상 상수 시간(O(1))에 가깝게 처리된다.
따라서 알고리즘의 전체 수행 시간은 제일 처음 간선을 가중치 기준으로 정렬하는 데 걸리는 시간인 O(E log E)가 된다.
경로 압축(Path Compression)
유니온 파인드(Union-Find) 알고리즘에서 Find 연산을 수행할 때 탐색한 모든 노드가 직접 루트 노드를 가리키도록 부모 정보를 갱신하는 최적화 기법
활용
크루스칼 알고리즘은 "모든 거점을 연결하되, 전체 구축 비용을 최소화한다"는 목적에 부합하는 다양한 실생활 문제에 활용된다.
- 인프라 및 네트워크망 구축: 여러 도시를 모두 잇는 통신망, 인터넷 광케이블, 상하수도 파이프라인 등을 설치할 때 전체 공사비용과 케이블 길이를 최소화하기 위해 사용된다.
- 도로망 설계: 고립되는 지역 없이 모든 마을을 연결하면서도 전체 도로 포장 비용을 최대한 아껴야 하는 상황에 적합하다.
즉, 특정 목적지까지의 빠른 도착이 아니라 전체 시스템을 하나로 연결하는 총비용의 효율성이 중요한 문제에서 핵심적인 해결책으로 작용한다.
4. 마치며
지금까지 그래프 문제라면 '다익스트라(Dijkstra)', '플로이드-워셜(Floyd-Warshall)', '위상 정렬(Topological Sort)' 정도만 알고 있어도 풀이에 충분하다고 생각했다. '최소 비용'이라는 키워드만 보고 반사적으로 다익스트라를 떠올렸던 것도 이러한 이유에서였다.
그래서 이번 크루스칼 알고리즘은 내게 큰 충격이었다. 그래프 유형에는 자신이 있었음에도, '특정 정점 기준의 탐색'과 '전체 간선 기준의 탐색'은 문제에 접근하는 패러다임 자체가 달랐다.
기존의 지식과 알고리즘들로는 도저히 이 문제를 해결할 접근 방법조차 떠올릴 수 없었다.
돌이켜보면, 신장 트리라는 개념을 몰랐던 것보다 더 근본적인 문제가 있었다. '최소 비용'이라는 키워드에 다익스트라를 기계적으로 대입해버린 순간, 그 외의 가능성을 탐색하는 사고 자체가 멈춰버렸다. 키워드와 알고리즘을 1:1로 매칭하는 방식에 익숙해질수록, 오히려 낯선 문제 앞에서 시야가 좁아진다는 걸 체감했다.
알고리즘 학습량을 늘리는 것도 중요하지만, 그보다 익숙한 템플릿에 문제를 끼워 맞추기 전에 "이 문제가 정말 요구하는 게 무엇인가"를 되묻는 습관을 길러야 겠다.
앞으로는 알고리즘 문제든 실무의 개발 문제든, 익숙한 패턴에 먼저 손이 가는 순간을 경계하려 한다. 정해진 템플릿에 갇힌 사고가 아니라, 문제의 본질을 파고드는 논리적 사고력 자체를 기르는 데 집중할 것이다.
