[프로그래머스] 42861. 섬 연결하기

문제 링크

[프로그래머스] 42861. 섬 연결하기

풀이 과정

MST 구현 문제입니다. 크루스칼과 프림 알고리즘을 사용해 풀었습니다. MST에 대한 설명은 여기에 있습니다.

코드

크루스칼

const solution = (n, costs) => {
    costs.sort((a, b) => a[2] - b[2]);
    let parent = Array.from({ length: n }, (val, idx) => idx);
    let rank = new Array(n).fill(0);

    const find = (x) => {
        if (parent[x] == x) return x;
        return (parent[x] = find(parent[x]));
    };

    const union = (x, y) => {
        let px = find(x),
            py = find(y);

        if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[px] = py;

            if (rank[px] == rank[py]) rank[px]++;
        }
    };

    let cnt = 0;
    let answer = 0;

    for (let idx in costs) {
        let a = find(costs[idx][0]);
        let b = find(costs[idx][1]);

        if (a == b) continue;

        union(a, b);
        answer += costs[idx][2];
        cnt++;

        if (cnt == n - 1) break;
    }

    return answer;
};

solution(4, [
    [0, 1, 1],
    [0, 2, 2],
    [1, 2, 5],
    [1, 3, 1],
    [2, 3, 8],
]);

프림

const solution = (n, costs) => {
    let visit = Array(n).fill(false);
    let pi = Array(n).fill(0);
    let key = Array(n).fill(Number.MAX_VALUE);
    let adj = Array.from(Array(n), () => Array(n).fill(0));

    for (let idx in costs) {
        let u = costs[idx][0];
        let v = costs[idx][1];
        let cost = costs[idx][2];

        adj[u][v] = adj[v][u] = cost;
    }

    pi[0] = -1;
    key[0] = 0;

    for (let i = 0; i < n; i++) {
        let min = Number.MAX_VALUE;
        let now = -1;

        for (let j = 0; j < n; j++) {
            if (!visit[j] && key[j] < min) {
                min = key[j];
                now = j;
            }
        }

        visit[now] = true;

        for (let next = 0; next < n; next++) {
            if (!visit[next] && adj[now][next] != 0 && adj[now][next] < key[next]) {
                pi[next] = now;
                key[next] = adj[now][next];
            }
        }
    }

    let answer = 0;
    for (let k of key) answer += k;

    return answer;
};

solution(4, [
    [0, 1, 1],
    [0, 2, 2],
    [1, 2, 5],
    [1, 3, 1],
    [2, 3, 8],
]);