[JS] 백준 1197번 : 최소 스패닝 트리 - 크루스칼 알고리즘, 서로소 집합, 최소비용 신장트리

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

이전에 포스팅했던 알고리즘을 활용한 문제이다.

https://ydoag2003.tistory.com/23

그래프 이론(크루스칼 알고리즘)

 

 

 

📋풀이방법

 

먼저 최소 스패닝 트리의 조건을 보자

• 최소 연결이란 간선의 수가 가장 적다는 것을 의미한다.
• 그래프에서 일부 간선을 선택해서 만든 트리.
• 모든 정점들이 연결 되어 있어야하고 사이클을 포함하면 안된다.
• 하나의 그래프에는 여러개의 신장 트리가 존재할 수 있다.

여기서 간선에 비용이 정해졌을 때 가장 비용이 적은 신장트리를 고르는 것이 최소비용 신장트리이다.

 

최소 스패닝 트리를 구성하는 간단한 방법은 바로 간선을 거리가 짧은 순으로 그래프에 포함시키면 된다.

 

1. 주어진 간선을 비용을 기준으로 오름차순한다.

2. 정렬된 간선을 차례대로 그래프에 포함시키되 사이클이 형성되는 경우 포함시키면 안된다.

3. 이때 이용하는 알고리즘은  Union-find 서로소집합 알고리즘 이다.

https://ydoag2003.tistory.com/22

그래프이론(서로소집합)

4. 모든 간선의 정보를 차례로 돌면서 사이클이 발생하지 않으면  간선의 비용을 누적한다.

5. 그리고 해당 간선은 사이클 테이블에 서로 union되었다고 갱신해준다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [ve, ...costs] = input;
let [V, E] = ve.split(" ").map(Number);
const arr = costs.map((a) => a.split(" ").map(Number));

arr.sort((a, b) => a[2] - b[2]);

const parent = [];
let answer = 0;

for (let i = 0; i < V; i++) parent.push(i); //사이클 테이블 선언

const getParent = (parent, x) => {
  //사이클테이블 정보 가져오기
  if (parent[x] === x) return x;
  return (parent[x] = getParent(parent, parent[x]));
};

const unionParent = (parent, x, y) => {
  //사이클 테이블 합쳐주기
  const n1 = getParent(parent, x);
  const n2 = getParent(parent, y);
  if (n1 < n2) return (parent[n2] = n1);
  else return (parent[n1] = n2);
};
//사이클이 발생하는지 안하는지 확인하는 함수
const findParent = (parent, x, y) => {
  //사이클테이블에서 두 값의 부모값이 같은지 확인하기
  const n1 = getParent(parent, x);
  const n2 = getParent(parent, y);
  if (n1 === n2) return true;
  else return false;
};

arr.forEach((tt) => {
  let [A, B, C] = tt;
  //모든 간선의 정보를 돌면서
  if (!findParent(parent, A, B)) {
    //사이클이 발생하지 않는 경우에만 그래프에 포함
    answer += C; //간선의 비용을 누적한다.
    unionParent(parent, A, B); //해당 간선을 사이클 테이블을 통해 합쳐준다.
  }
});

console.log(answer);

 

 

 

💢어려웠던 점

1. 최소 스패닝 트리 == 최소 비용 신장 트리 == 크루스칼 알고리즘 => 서로소 집합(union-find 알고리즘)사용 임을 알아야한다.

- 처음에 최소 스패닝 트리가 뭔지 파악하지 못했다.

-이전 포스팅에서 크루스칼알고리즘을 배워서 union-find알고리즘을 사용했다.

-아직 union-find 알고리즘을 외우지 못했다. 다시 한번 확인해야겠다.