[백준1647_자바스크립트(javascript)] - 도시 분할 계획

🔴 문제

도시 분할 계획

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const graph = inputs.sort((a, b) => a[2] - b[2]);
const p = Array.from({ length: n + 1 }, (_, idx) => idx);

const find = (a) => {
  if (a !== p[a]) p[a] = find(p[a]);

  return p[a];
};

const union = (a, b) => {
  const pa = find(a);
  const pb = find(b);

  p[pb] = pa;
};

const ans = [0];
for (const [s, e, c] of graph) {
  const ps = find(s);
  const pe = find(e);

  if (ps === pe) continue;
  union(s, e);
  ans.push(c);
}

ans.pop();

console.log(ans.reduce((pre, cur) => pre + cur));

🟢 풀이

⏰ 소요한 시간 : -

문제에서 요구하는 조건은 두개다.
1. 마을을 두개로 분리해야한다.
2. 모든 마을은 연결된 통로가 있어야하며 최단 거리를 구해야 한다.

여기서 1번 조건을 빼면 모든 마을을 최단거리로 연결했을때의 거리의 합을 구하는 것이고 이는 최소 스패닝 트리임을 쉽게 알 수 있다.

그렇다면 최소 스패닝 트리를 두개로 분할하는 방법은 ? 가장 마지막에 추가된 간선만 제거해주면 된다!

최소스패닝 트리를 구하기 위한 find, union함수를 정의해주고, 간선 정보를 가중치 순으로 오름차순 정렬해준 뒤 최소 스패닝 트리를 구해주면 된다.
이 과정을 마치고 나면 ans에는 선택된 간선이 오름차순으로 들어가 있을 텐데 가장 긴 간선인 마지막 간선을 pop해주면 정답 간선들이 나온다.
이 값들을 모두 더해 출력해주면 끝!

🔵 Ref