코딩 테스트는 프로그래밍 능력을 평가하는 좋은 방법입니다. 오늘은 최소 신장 트리(MST) 문제를 해결하는 방법에 대해 알아보겠습니다.
이 문제는 다양한 분야에서 활용되며, 특히 컴퓨터 네트워크와 관련된 문제에서 자주 등장합니다.
최소 신장 트리를 구축하는 알고리즘은 여러 개가 있지만, 특히 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim’s Algorithm)이 많이 사용됩니다.
문제 설명
아래 그래프를 나타내는 간선이 주어졌을 때, 최소 신장 트리를 구하는 문제를 해결해 보겠습니다.
각 간선의 가중치가 부여되어 있으며, 전체 가중치의 합이 최소가 되도록 연결된 그래프를 찾아야 합니다.
문제 정의
입력:
[(1, 2, 4), (1, 3, 1), (2, 3, 2), (2, 4, 5), (3, 4, 8), (1, 4, 3)]
출력:
최소 신장 트리의 간선 리스트: [(1, 3, 1), (2, 3, 2), (1, 4, 3), (2, 4, 5)]
최소 가중치의 합: 11
문제 풀이 과정
1단계: 그래프 데이터 구조 이해하기
그래프는 정점(노드)와 간선으로 이루어져 있습니다.
여기서는 간선이 튜플의 형태로 `(시작 정점, 끝 정점, 가중치)`로 주어집니다.
우리는 이 데이터를 이용해 그래프를 구성해야 합니다.
2단계: 간선 정렬하기
크루스칼 알고리즘은 먼저 간선을 가중치를 기준으로 정렬합니다.
와 함께 주어진 간선 리스트를 오름차순으로 정렬하여 최소 가중치의 간선을 선택할 수 있도록 합니다.
3단계: Union-Find 구조로 사이클 검사하기
간선을 추가할 때 사이클이 발생하는지를 확인하기 위해 Union-Find 자료구조를 사용합니다.
이 자료구조는 두 가지 주요 기능을 가지고 있습니다:
- Find: 특정 요소가 어떤 집합에 속하는지 찾기
- Union: 두 요소가 속하는 집합을 합치기
사이클이 발생하지 않으면 간선을 선택하고, 그렇지 않으면 간선을 무시합니다.
알고리즘을 구현하는 데 필요한 기본적인 Union-Find 클래스와 그 메서드를 정의합니다.
4단계: MST 구현하기
이제 모든 단계의 구현을 결합하여 최종적으로 MST를 구해보겠습니다.
아래는 자바스크립트로 구현한 크루스칼 알고리즘의 예시입니다.
class UnionFind {
constructor(size) {
this.parent = Array.from({length: size}, (_, index) => index);
this.rank = Array(size).fill(1);
}
find(node) {
if (this.parent[node] !== node) {
this.parent[node] = this.find(this.parent[node]);
}
return this.parent[node];
}
union(node1, node2) {
const root1 = this.find(node1);
const root2 = this.find(node2);
if (root1 !== root2) {
if (this.rank[root1] > this.rank[root2]) {
this.parent[root2] = root1;
} else if (this.rank[root1] < this.rank[root2]) {
this.parent[root1] = root2;
} else {
this.parent[root2] = root1;
this.rank[root1]++;
}
}
}
connected(node1, node2) {
return this.find(node1) === this.find(node2);
}
}
function kruskal(edges, numVertices) {
edges.sort((a, b) => a[2] - b[2]); // 간선들을 가중치 기준으로 정렬
const uf = new UnionFind(numVertices);
const mst = [];
let totalWeight = 0;
for (const [u, v, weight] of edges) {
if (!uf.connected(u - 1, v - 1)) {
uf.union(u - 1, v - 1);
mst.push([u, v, weight]);
totalWeight += weight;
}
}
return { mst, totalWeight };
}
const edges = [
[1, 2, 4],
[1, 3, 1],
[2, 3, 2],
[2, 4, 5],
[3, 4, 8],
[1, 4, 3]
];
const numVertices = 4;
const { mst, totalWeight } = kruskal(edges, numVertices);
console.log("최소 신장 트리의 간선 리스트:", mst);
console.log("최소 가중치의 합:", totalWeight);
5단계: 결과 분석하기
구현된 알고리즘을 통해 얻어진 결과는 다음과 같습니다.
최소 신장 트리의 간선 리스트 및 전체 가중치를 확인하여 알고리즘이 제대로 작동하는지 분석합니다.
결과적으로, 주어진 간선을 기준으로 최소 신장 트리를形成하는 데 성공했습니다.
- 최소 신장 트리의 간선 리스트: [(1, 3, 1), (2, 3, 2), (1, 4, 3), (2, 4, 5)]
- 최소 가중치의 합: 11
결론
오늘은 자바스크립트를 사용하여 최소 신장 트리 문제를 해결하는 방법을 살펴보았습니다.
주어진 간선 리스트를 통해 여러 알고리즘을 적용할 수 있으며, 이 과정에서 그래프의 특성 또한 이해할 수 있습니다.
이러한 문제를 풀어 나가면서 알고리즘의 성능 분석 및 최적화에 대한 경험을 쌓을 수 있으며,
실제 코딩 테스트에서 출제될 가능성이 높은 주제이므로 충분히 연습해보시기 바랍니다.