[Programmers] 섬 연결하기

문제

 

탐욕법(Greedy) > 섬 연결하기

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

 

 

아이디어

 

이번 문제의 아이디어는 MST입니다.

 

소주제는 Greedy로 되어있지만 저는 MST에 더 적합한 문제라고 개인적으로 생각합니다.

 

MST기법들인 프림이나 크루스칼 중 아무거나 사용해도 문제없이 풀 수 있을 것으로 보입니다.

 

저는 크루스칼을 이용하여 구현을 해봤습니다.

 

 

구현 코드 (JavaScript)

 

class Node {
    constructor(a, b, val) {
        this.a = a;
        this.b = b;
        this.val = val;
    }
}

function solution(n, costs) {
    const nodes = [];
    
    for(let i=0; i<costs.length; i++) {
        const cost = costs[i];
        const node = new Node(cost[0], cost[1], cost[2]); // a ↔ b간 이동을 위한 비용은 val
        nodes.push(node);
    }
    
    nodes.sort((a, b) => a.val - b.val); // 비용이 작은 순서대로 정렬
    
    const p = []; // 인덱스별 부모인덱스를 담는 배열
    const rank = []; // 인덱스의 랭크(=depth)를 담는 배열
    
    for(let i=0; i<n; i++) {
        p.push(i); // 인덱스별 부모인덱스는 자기자신으로 초기화
        rank.push(0); // 랭크는 모두 0으로 초기화
    }
    
    let count = 0; // 다리가 연결된 개수
    let res = 0; // 다리를 연결하기 위해 소모된 비용
    
    while(count < n-1) { // 크루스칼 알고리즘
        const node = nodes.shift();
        let pa = node.a;
        let pb = node.b;
        
        while(p[pa] != pa) {
            pa = p[pa];
        }
        
        while(p[pb] != pb) {
            pb = p[pb];
        }
        
        if(pa != pb) {
            if(rank[pa] > rank[pb]) {
                p[pb] = pa;
            } else {
                if(rank[pa] === rank[pb]) {
                    rank[pb]++;
                }
                p[pa] = pb;
            }
            
            count++;
            res = res + node.val;
        }
    }
    
    return res;
}

 

 

 

읽어주셔서 감사합니다.