[JavaScript] 프로그래머스 섬 연결하기 LEVEL3

문제출처

const isCycle = (cycle) => {
    for (let i=1; i<cycle.length; i++) {
        if (cycle[i-1] !== cycle[i]) return false;
    }
    return true;
};

const changeCycle = (cycle, a, b) => {
    const na = cycle[a];
    const nb = cycle[b];
    for (let i=0; i<cycle.length; i++) {
        if (cycle[i] === nb) cycle[i] = na;
    }
    return cycle;
};

function solution(n, costs) {
    let answer = 0;
    let cycle = Array(n).fill(0).map((e, i) => i);
    costs.sort((a, b) => a[2] - b[2]);
    
    while (!isCycle(cycle)) {
        const [a, b, cost] = costs.shift();
        if (cycle[a] !== cycle[b]) {
            cycle = changeCycle(cycle, a, b);
            answer += cost;
        }
    }
    
    return answer;
}

풀이

• 오름차순으로 정렬해주는게 뽀인트
• 다리가 모두 연결되었을때 while문 탈출 -> isCycle
• 두 다리를 연결시키면서
  • 두 다리의 cycle값을 같게 만들고
  • 두 다리 중 한쪽 다리와 cycle값이 같은 (이미 연결된) 다른 다리들의 cycle값도 같게 만들어준다.
• 두 다리를 연결시키면서 answer에 cost를 더한다.

풀이 참고