섬 연결하기

programmers.co.kr/learn/courses/30/lessons/42861?language=javascript

코딩테스트 연습 - 섬 연결하기

function solution(n, costs) {
    let answer = 0;
    let isLand = {}; // 섬 정보
    let bridge = {}; // 다리 정보
    let total = 0; // 지어진 다리 갯수
    
    costs.sort((a, b) => a[2] - b[2]);
    isLand[costs[0][0]] = true;
    isLand[costs[0][1]] = true;
    bridge[0] = true;
    answer += costs[0][2];
    total += 2;
    
    while (total < n) {
        for (let i = 1; i < costs.length; i++) {
            let [start, end, cost] = costs[i];
            if (!bridge[i] && ((isLand[start] && !isLand[end]) || (!isLand[start] && isLand[end]))) {
                isLand[start] = true;
                isLand[end] = true;
                bridge[i] = true;
                answer += cost;
                total++;
                break;
            }
        }
    }
    return answer;
}