[백준21924_자바스크립트(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 edges = 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;
};

let ans = edges.reduce((pre, cur) => pre + cur[2], 0);
for (const [s, e, c] of edges) {
  const ps = find(s);
  const pe = find(e);

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

for (let i = 1; i <= n; i++) {
  find(i);
}

if (new Set(p).size === 2) console.log(ans);
else console.log(-1);

🟢 풀이

⏰ 소요한 시간 : -

대놓고 나 최소신장트리에요~~ 하는 문제
다만 문제에서 모든 집이 연결되어 있다는 조건이 없다. 즉 최소신장트리를 구하지 못할 수 있다. 이 부분만 확인해주면 쉽게 풀이할 수 있다.

최소신장 트리 문제에 맞게 union, find 함수를 각각 구현해준 뒤, 정렬한 edges 간선들을 돌며 최소신장트리의 간선을 선택한다.
이 때 문제에서는 감축되는 비용의 값을 물어봤으므로 ans의 초기값으로 모든 간선의 가중치 합을 구한 뒤 선택한 간선의 가중치를 빼줬다.

마지막으로 최소신장트리가 만들어졌는지 확인하기 위해 i부터 n까지 find연산을 수행한 뒤 set으로 변환하여 길이가 2인지 아닌지에 따라 결과를 출력한다.

🔵 Ref