2887번 - 행성 터널

1️⃣ Kruskal's Algorithm

 

✏️ 풀이 과정

문제의 서술을 읽어보면 의아한 점을 느낄 수 있는데 분명 난이도가 플래티넘 5임에도 일반적인 크루스칼 알고리즘의 구현을 요구하고 있기 때문입니다. 그러나 N의 크기를 보면 난이도가 책정된 이유를 알 수 있습니다.

 

일반적으로 떠올리게 되는 방법은 N개의 정점이 주어질 때 다른 모든 정점과 연결하는 간선을 만들고 해당 간선을 정렬해서 크루스칼 알고리즘을 적용하는 것입니다. 그러나 이 간선을 만드는 과정이 N + N-1 + ... +1 로 O(N^2)이기 때문에(등차수열의 합) 시간 초과가 발생하게 됩니다. 따라서 간선의 개수를 줄일 아이디어가 필요합니다.

 

간선의 개수를 줄이는 방법은 브랜치 앤 바운드에서 하는 것과 비슷하게 유망한 조합만을 사용하는 것입니다. 기본적인 아이디어는 두 정점이 서로 인접해있다면 적어도 x, y, z축 중 하나에서는 가장 가까운 거리를 가진다는 것입니다. 따라서 x축, y축, z축을 각각 기준으로 정점들을 정렬하고 인접한 정점끼리만 간선을 만들어서 저장하면 간선의 개수를 N의 배수로 줄일 수 있어 시간 복잡도가 O(N)으로 변하게 됩니다.

 

위에서 유망한 간선들을 모두 구했다면 N-1개의 간선이 연결될 때까지 union을 진행하면 됩니다. 사이클을 형성하지 않고 두 정점이 연결되었을 때의 비용만 모두 더하면 답을 얻을 수 있습니다.

 

⏱ 시간 복잡도

크루스칼 알고리즘의 시간 복잡도 O(NlogN)이 전체 시간 복잡도가 됩니다.

 

💻 코드

JavaScript

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

const N = Number(input[0]);
const planets = [];
for (let i = 1; i <= N; i++) {
    const planet = input[i].split(" ").map(Number);
    planet.push(i - 1);
    planets.push(planet);
}

const getCost = (a, b) => {
    return Math.min(
        Math.abs(a[0] - b[0]),
        Math.abs(a[1] - b[1]),
        Math.abs(a[2] - b[2])
    );
};

const edges = [];
planets.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < N - 1; i++) {
    edges.push([
        planets[i][3],
        planets[i + 1][3],
        getCost(planets[i], planets[i + 1]),
    ]);
}
planets.sort((a, b) => a[1] - b[1]);
for (let i = 0; i < N - 1; i++) {
    edges.push([
        planets[i][3],
        planets[i + 1][3],
        getCost(planets[i], planets[i + 1]),
    ]);
}
planets.sort((a, b) => a[2] - b[2]);
for (let i = 0; i < N - 1; i++) {
    edges.push([
        planets[i][3],
        planets[i + 1][3],
        getCost(planets[i], planets[i + 1]),
    ]);
}

const parents = Array.from(Array(N), (_, i) => i);
const ranks = Array.from(Array(N), () => 1);
const find = (a) => {
    if (parents[a] === a) {
        return a;
    }
    return (parents[a] = find(parents[a]));
};
const union = (a, b) => {
    let aRoot = find(a);
    let bRoot = find(b);

    if (aRoot === bRoot) return false;
    if (ranks[aRoot] < ranks[bRoot]) [aRoot, bRoot] = [bRoot, aRoot];

    parents[bRoot] = aRoot;
    if (ranks[aRoot] === ranks[bRoot]) ranks[aRoot]++;

    return true;
};

let ans = 0;
let cnt = 0;
edges.sort((a, b) => a[2] - b[2]);
for (let i = 0; i < edges.length; i++) {
    if (union(edges[i][0], edges[i][1])) {
        ans += edges[i][2];
        if (++cnt === N - 1) break;
    }
}

console.log(ans);