오늘은 알고리즘 테스트에서 자주 등장하는 문제 중 하나인 ‘최소 신장 트리(MST, Minimum Spanning Tree)’를 구하는 방법에 대해 알아보겠습니다. 특히, 자바스크립트를 사용하여 이 문제를 해결하는 방법을 단계별로 설명하도록 하겠습니다. 이 강좌를 통해 여러분은 모든 개념을 이해하고, 실제 코딩테스트에서도 자신있게 이 문제를 해결할 수 있는 능력을 기르게 될 것입니다.
1. 최소 신장 트리란?
최소 신장 트리는 연결 그래프에서 정점들을 모두 포함하는 부분 그래프이며, 그 부분 그래프의 간선 비용의 합이 최소가 되는 그래프입니다. 즉, 모든 정점이 연결되어 있으면서 최소한의 비용으로 연결된 트리를 의미합니다. MST는 네트워크 설계, 교통 시스템, 클러스터링 등 다양한 분야에서 활용됩니다.
2. 문제 설명
주어진 그래프의 정점과 간선 정보가 있을 때, 최소 신장 트리를 구하고 그 총 가중치를 반환하는 함수를 작성하세요.
입력 형식
- 정점의 개수 n (1 ≤ n ≤ 1000)
- 간선의 개수 m (1 ≤ m ≤ 10000)
- 각 간선은 (a, b, c)의 형태로 주어지며, a와 b는 정점, c는 간선의 가중치입니다.
출력 형식
최소 신장 트리의 총 가중치를 출력합니다.
예시
입력:
4 5
1 2 1
1 3 4
2 3 2
1 4 3
3 4 5
출력:
6
3. 알고리즘 선택
최소 신장 트리를 구하는 방법에는 여러 가지가 있습니다. 그 중에서도 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim’s Algorithm)이 널리 사용됩니다. 여기서는 크루스칼 알고리즘을 사용할 것입니다.
크루스칼 알고리즘
크루스칼 알고리즘은 간선을 기준으로 정렬한 후, 가장 낮은 가중치의 간선부터 선택하여 사이클을形成하지 않는 한에서 최소 신장 트리를 만들 수 있도록하는 방식입니다. 이 방법은 주어진 간선 목록을 먼저 정렬한 뒤, 가장 가벼운 간선부터 추가해 나가는 방식입니다.
4. 알고리즘 구현
이제 크루스칼 알고리즘을 이용하여 문제를 해결하는 자바스크립트 코드를 작성해 보겠습니다. 전체 단계는 다음과 같습니다:
- 간선 정보를 입력받은 후, 가중치 기준으로 정렬합니다.
- 유니온-파인드(Union-Find) 자료구조를 활용하여 사이클이 형성되지 않도록 간선을 포함합니다.
- 모든 간선을 처리한 후, 최소 신장 트리의 총 가중치를 계산하여 반환합니다.
코드 구현
function find(parent, i) {
if (parent[i] === -1) {
return i;
}
return find(parent, parent[i]);
}
function union(parent, x, y) {
const xset = find(parent, x);
const yset = find(parent, y);
parent[xset] = yset;
}
function kruskal(n, edges) {
edges.sort((a, b) => a[2] - b[2]); // 간선 가중치 기준으로 정렬
let parent = Array(n + 1).fill(-1);
let minWeight = 0;
const mst = [];
for (let i = 0; i < edges.length; i++) {
const [u, v, weight] = edges[i];
if (find(parent, u) !== find(parent, v)) {
union(parent, u, v);
minWeight += weight;
mst.push([u, v, weight]);
}
}
return { minWeight, mst };
}
// 예시 입력 데이터
const n = 4;
const edges = [
[1, 2, 1],
[1, 3, 4],
[2, 3, 2],
[1, 4, 3],
[3, 4, 5]
];
const result = kruskal(n, edges);
console.log("최소 신장 트리의 총 가중치:", result.minWeight);
5. 코드 해설
위 코드는 크루스칼 알고리즘을 사용하여 주어진 그래프의 최소 신장 트리를 구하는 함수입니다. 다음과 같은 주요 부분으로 나뉩니다:
5.1. 유니온-파인드 함수
유니온-파인드(Union-Find) 자료구조는 그래프의 연결 성분을 추적하는 데 사용됩니다. 각 노드는 자신의 부모를 가지고 있습니다. find 함수는 노드가 속한 집합의 대표자를 찾고, union 함수는 두 집합을 합칩니다.
5.2. 간선 정렬
간선 목록을 가중치 기준으로 정렬하여 최소 가중치의 간선부터 선택할 수 있도록 합니다. 자바스크립트의 sort 메서드를 사용하여 간단히 정렬할 수 있습니다.
5.3. 최소 신장 트리 구성
각 간선에 대해 두 노드의 부모를 확인하여 사이클이 생기지 않는 경우에만 그 간선을 선택합니다. 선택된 간선은 mst 배열에 저장되며, 가중치의 합은 minWeight 변수에 증가합니다.
6. 성능 분석
크루스칼 알고리즘의 시간 복잡도는 O(E log E)입니다. 여기서 E는 간선의 수입니다. 주어진 문제의 제약 사항 하에서 이 알고리즘은 효율적입니다. 유니온-파인드의 경로 압축 기법을 사용할 경우 추가적인 성능 향상을 기대할 수 있습니다.
7. 마무리
이번 강좌에서는 자바스크립트를 사용하여 최소 신장 트리를 구하는 크루스칼 알고리즘에 대해 알아보고, 문제를 해결하는 방법에 대해 상세히 설명하였습니다. 그래프 문제들은 알고리즘 경진대회 및 여러 코딩 테스트에서 빈번히 출제되므로, 여러분이 익혀두면 많은 도움이 될 것입니다. 다음에는 다른 알고리즘이나 데이터 구조를 활용하여 다양한 문제를 함께 풀어보도록 하겠습니다.
8. 연습 문제
아래의 문제를 풀어보세요. 문제를 해결한 후에 자신의 코드를 리뷰하여 최적화할 수 있는 부분이 있는지 점검해 보세요.
주어진 그래프에서 최소 신장 트리의 간선을 추출한 후, 이 간선의 가중치 목록과 함께 출력하는 알고리즘을 작성하세요.