[백준 #1197] 최소 스패닝 트리, 자바스크립트 풀이

문제 난이도	유형
🥇골드 4티어	그래프, 최소 신장 트리, 유니온 파인드 알고리즘

 

문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	54980	23231	13075	40.511%

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

예제 입력

3 3
1 2 1
2 3 2
1 3 3

 

예제 출력

3

---

풀이

최소 신장 트리(minimum spanning tree)의 가중치를 물어보는 문제이다. 신장 트리는 그래프의 최소 연결 부분 그래프다. 쉽게 말하면 모든 정점이 이어지는 최소 연결 그래프이다. 즉, Vertext - 1 개의 간선을 가지는 연결 그래프이다. 그중 최소 신장 트리는 간선의 가중치 합이 최소인 신장 트리다. 위 문제는 union-find 알고리즘과 크루스칼 알고리즘을 사용해서 풀이할 수 있다.

 

문제의 입력 예시 참고

최소 신장 트리 문제 유의 사항

간선과 서로소 집합의 데이터가 필요하고, 탐욕적으로 풀기 위해 간선을 정렬하고 시작해야 한다. 또한 Union-Find 알고리즘을 이용해 순환이 발생하지 않도록 한다. 자신이 속한 집합의 최상위 요소가 같으면 연결되어 있다는 것을 잊지 말자.

 

코드

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", function (line) {
  input.push(line.split(" ").map(Number));
}).on("close", function () {
  solution(input.shift(), input);
  process.exit();
});

function solution([V, E], costs) {
  let count = 0;
  const sortedCosts = costs.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: V }, (_, i) => i);

  const find = (parent, x) => {
    if (parent[x] === x) return x;
    return (parent[x] = find(parent, parent[x])); //경로 압축
  };

  const union = (parent, a, b) => {
    a = find(parent, a);
    b = find(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
  };

  const compare = (parent, a, b) => {
    a = find(parent, a);
    b = find(parent, b);
    return a === b;
  };

  for (const [a, b, cost] of sortedCosts) {
    if (!compare(parent, a, b)) {
      count += cost;
      union(parent, a, b);
    }
  }
  console.log(count);
}