[Programmers] 섬 연결하기 (Lv 3, JavaScript)

[ 학습 내용 ]
최소치의 다리를 선택하면서 진행하되, 다리를 통해 연결되는 섬이 이미 연결되었는지를 판별해야한다.

 

처음 시도는, 단순하게 다리를 놓을 때 양 쪽 섬을 방문했었는지 판별했다.

그러나, 이는 서로 각각 연결된 두 그룹을 이을 때, 이미 모든섬이 방문했으므로 다리를 놓지 않아 마지막 연결에 실패한다.

 

다음 시도로, UnionFind를 활용하여 다리를 놓는 두 섬의 부모를 판단해 겹치는지 판단하는 것이다.

만약 겹친다면, 그 연결될 섬은 Cycle이 발생하고

겹치지 않는다면, 그 연결될 섬은 처음 연결되는 섬이므로 연결해준다.

 

여기서 그래프의 Cycle을 판단할 때, UnionFind가 가장 빠르고 편한방법인지 추후 확인하여 활용하려 한다.

[ 소스 코드 ]

function solution(n, costs) {
    const unionFind = (n, parent) => {
        if (parent[n] === n) return n;
        return parent[n] = unionFind(parent[n], parent);
    }
    
    let answer = 0;
    let parent = new Array(n).fill(0);
    parent = parent.map((_, idx) => idx);
    
    costs.sort((o1, o2) => o1[2] - o2[2]);
    
    costs.forEach((cost, index) => {
        let st = unionFind(cost[0], parent);
        let ed = unionFind(cost[1], parent);
        
        if (st !== ed) {
            answer += cost[2];
            parent[st] = ed;
        }
    })
    
    return answer;
}