[프로그래머스 Lv.3] 알고리즘 고득점 Kit 탐욕법(Greedy) - 섬 연결하기

✨ 정답 ✨

class UnionFind {
    constructor(n) {
        this.parent = new Array(n).fill().map((_, i) => i);
    }

    find(x) {
        if (this.parent[x] === x) return x;
        return this.parent[x] = this.find(this.parent[x]);
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootY] = rootX;
            return true; 
        }
        return false; 
    }
}

function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]); 
    const uf = new UnionFind(n);
    let answer = 0;
    let connected = 0;

    for (let cost of costs) {
        const [island1, island2, weight] = cost;
        if (uf.union(island1, island2)) {
            answer += weight;
            connected++;
            if (connected === n - 1) break; 
        }
    }

    return answer;
}

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡