프로그래머스_섬연결하기

다차원 배열 정렬과 크루스칼 알고리즘을 사용하는 문제이다. 

 

다차원 배열 정렬하는법

 var costs = [[1, 2, 3], [1, 2, 3], [2, 3, 4]]
 // a[n] - b[n] => 배열의 n 을 기준으로 정렬한다.
 costs.sort((a, b) => {
        return a[2] - b[2];
    })

다음은 전체 코드이다.

function solution(n, costs) {
    var answer = 0;
    var parent = [];
    for(let i = 0; i < n; i++){
        parent.push(i);
    }
    costs.sort((a, b) => {
        return a[2] - b[2];
    })
    var cnt = 0;
    for(let i = 0; i < costs.length; i++){
        var a = find(parent, costs[i][0]);
        var b = find(parent, costs[i][1]);
        var l = costs[i][2];
        if(a != b){
            if(a < b){
                parent[b] = a;
            }else{
                parent[a] = b;
            }
            cnt++;
            answer += l;
        }
        if(cnt == n - 1){
            break;
        }
    }


    return answer;
}

function find(parent, a){
    if(parent[a] === a){
        return a;
    }
    return parent[a] = find(parent, parent[a]);
}