(프로그래머스 JS)섬 연결하기

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

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

union & find를 이용한 문제 풀이.

 

우선 parent를 저장하는 n 크기의 배열을 선언하여 자기 자신을 가리키도록 한다.

이후 costs를 비용의 오름차순으로 정렬.

for문으로 costs를 순회.

costs[0]은 출발점, costs[1]은 도착점이므로 unionFind 함수에 각 노드 번호를 전달해 parent를 찾는다.

만약 n번의 노드의 부모가 n이라면 그대로 n을 리턴해주고,

그렇지 않다면 루트의 번호를 계속 갱신해주도록 한다.

 

갱신이 끝나서 for문으로 다시 돌아와 if문을 검사한다.

start와 end => 시작점의 부모 번호와 도착점의 부모 번호가 같지 않다면 최소 비용으로 한번도 가지 않은 다리를 최소 비용으로 건넜다는 의미가 되기 때문에 answer += costs[i][2]를 더해준다.

또한, 이미 건넜다는 표시를 위해 parent[start] = end로 다시 갱신해주면 된다.

const unionFind = (n, parent) => {
    if(parent[n] === n){
        return n;
    }
    
    return parent[n] = unionFind(parent[n], parent);
}

const solution = (n, costs) => {
    let answer = 0;
    
    const parent = Array(n).fill(0);
    
    for(let i = 0; i < n; i++){
        parent[i] = i;
    }
    
    costs.sort((a, b) => a[2] - b[2]);
    
    for(let i = 0; i < costs.length; i++){
        const start = unionFind(costs[i][0], parent);
        const end = unionFind(costs[i][1], parent);
        const cost = costs[i][2];
        
        if(start !== end){
            answer += cost;
            parent[start] = end;
        }
    }
    
    return answer;
}