[JS/알고리즘] 탐욕 : 섬 연결하기 (프로그래머스)

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

문제 풀이

우선 최소 비용이 되어야하므로 비용순 오름차순 정렬 해준다.

가장 적은 비용의 간선 부터 연결해 나가면서 불필요하게 중복 연결되어 사이클을 형성시키는 간선 연결하지 않는다.

 

크루스칼 알고리즘은 이 문제의 그래프와 같은 최소 비용 신장 트리를 만드는 알고리즘으로,

어떤 노드가 연결된 루트에서 가장 작은 인덱스의 노드를 부모라고 하고, 여러 노드 간 부모가 같다면 이 들이 연결되어 있다고 볼 수 있다.

 

예시

모든 노드 들은 최초에는 자기 자신을 가리키고 있지만,

다음과 같은 최소 비용 신장트리의 경우, 연결이 이루어지면서 모든 노드가 최종 부모로 1을 가리키게 된다.

 

만약 5와 6이 가장 비용이 작아 최초로 연결되었다고 할 때, 값은 {5 : 5, 6: 5}가 된다.

그리고 2와 6이 연결된다고 할 때, 6의 부모(5)와 2의 부모(2)를 비교해 더 큰 노드인 5에 상대 노드의 값 2를 넣는다.

즉, {6 : 5, 5 : 2, 2 : 2}로 바뀌게 된다. 해당 오브젝트에서 6이 5를 가르키고 있지만, 5는 2를 가르키고 있다.

결과적으로 6의 최종 부모는 2가 된다. 이를 위해 크루스칼에서는 getParent 재귀 함수가 있으며, 부모를 비교해 노드의 값을 바꿔주는

union 함수도 함께 존재한다.

 

getParent와 union, 그러니까 해당 노드의 최종 부모 값을 찾고 노드의 특정 루트에 추가하는 알고리즘 기법을 유니온-파인드 라고 한다.

유니온-파인드로는 그래프에서 몇 개의 독립된 그룹이 있는지를 판단할 수 있지만, 크루스칼 알고리즘에서 사용 되는 경우는 노드의 연결 여부를 판단하는 용도로 사용된다. 다시 말해 크루스칼은 유니온-파인드를 포함하고 있다.

 

긴 설명보다 아래의 영상 두 개를 보고나면 해당 문제가 쉽게 풀릴 것이다.

해당 두 알고리즘은 그래프에서 기초적인 알고리즘으로 익혀두는 것이 좋겠다.

크루스칼

유니온-파인드

 

 

해결 코드

//사이클이 발생하면 안됨
//최소 비용

let p = {};

function getParent(e){
    if(p[e]===e){
        return e;
    }else{
        return find(p[e]);
    }
}

function union(e){
    let a = getParent(e[0]);
    let b = getParent(e[1]);

    if(a===b){
        return -1;
    }else{
        if(a>b){
            p[a] = b;
        }else{
            p[b] = a;
        }
    }
    return e[2];
}

function solution(n, costs) {
    var answer = 0;
    
    //오름차순 정렬
    costs.sort(function(a,b){
               return a[2]-b[2];
               })
    
    //object 생성
    for(let i =0; i<n; i++){
        p[i] = i;
    }
    
    costs.map((e)=>{
        let cost = union(e);
        if(cost!==-1){
        answer += cost;
        }
    })
    return answer;
}

 

크루스칼과 유니온-파인드의 설명이 장황한 것과 달리

솔직히 이해만 한다면 코드 자체는 매우 간단하다.

노드가 연결 되기전 두 노드의 부모(value가 자기 자신인 노드)를 찾고, 두 노드가 같다면 불필요한 연결이다.

같지 않다면 두 노드를 연결하는데, 두 노드의 부모를 더 작은 값으로 통일시켜 두 노드의 연결을 표현한다.

그리고 모든 간선 들의 검토가 끝나거나 간선 개수가 노드 개수 - 1이라면 종료하면 된다.

굳이 종료 조건을 걸지 않아도 모든 노드가 연결된 후에는 유니온-파인드에 의해 나머지 간선의 연결은 이루어지지 않는다.