🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], ...inputs] = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number));
const edges = [];
const p = Array.from({ length: n + 1 }, (_, idx) => idx);
let X = [];
let Y = [];
let Z = [];
for (let i = 0; i < n; i++) {
const [x, y, z] = inputs[i];
X.push([x, i]);
Y.push([y, i]);
Z.push([z, i]);
}
X = X.sort((a, b) => a[0] - b[0]);
Y = Y.sort((a, b) => a[0] - b[0]);
Z = Z.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < n - 1; i++) {
edges.push([X[i][1], X[i + 1][1], X[i + 1][0] - X[i][0]]);
edges.push([Y[i][1], Y[i + 1][1], Y[i + 1][0] - Y[i][0]]);
edges.push([Z[i][1], Z[i + 1][1], Z[i + 1][0] - Z[i][0]]);
}
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 = 0;
for (const [s, e, c] of edges.sort((a, b) => a[2] - b[2])) {
const ps = find(s);
const pe = find(e);
if (ps === pe) continue;
union(s, e);
ans += c;
}
console.log(ans);🟢 풀이
⏰ 소요한 시간 : -
최소 스패닝 트리유형이다.
최소 스패닝 트리는 모든 정점을 이은 여러 트리중 가중치가 최소인 트리를 말한다. 최소 스패닝 트리를 구하기 위해서 크루스칼 알고리즘으로 풀이했다.
다만 이 문제에서 정점이 될 수 있는 최대 개수는 100,000개이다. 이 최대 개수가 모두 이어져 있다고 가정했을 경우 100,000 * 99,999 / 2 이므로 시간초과가 발생한다. 뿐만아니라 모든 간선을 [시작값, 끝값, 코스트]형식으로 저장하면 24(8 * 3) 바이트가 필요하다. 즉, 100,000 * 99,999 / 2 * 24 만큼의 메모리가 필요한다. 메모리 초과도 발생한다.
그래서 풀이를 보고 풀었다 ^-^
문제를 보면 두 행성간의 가중치를 구하는 공식을 다음과 같이 정의했다.
min(|xA-xB|, |yA-yB|, |zA-zB|)이 말은 행성의 각 좌표를 정렬한다면 인접한 두 행성의 거리가 최소 스패닝 트리 간선의 후보가 된다는 말이다.
4개의 행성이 있고, 각 행성의 x 좌표는 [6, 3, 1, 8]이라고 가정해보자
이 행성들로부터 얻을 수 있는 가중치 |xA-xB|의 조합을 구하려면 6-3, 6-1, 6-8, 3-1, 3-8, 1-8 총 6가지가 나올 것이다.
하지만 이를 x좌표 기준으로 정렬해 [1, 3, 6, 8]으로 만든다면
1-3, 3-6, 6-8 이 세 값중에 무조건 최소값이 나온다.
이 값을 X, Y, Z 세 방향에서
즉 다음과 같이 풀이했다.
1. x, y, z 좌표를 모두 분리해 저장한다.
2. 분리한 좌표를 정렬해 각 좌표간의 간격을 edges에 넣는다.
3. 이 edges로 최소 스패닝 트리를 찾는다.
레퍼런스로 걸어둔 링크를 보고 풀이했는데 레퍼런스를 보면 더 잘 이해될듯..!
🔵 Ref
