[프로그래머스] 섬 연결하기

November 15, 2023

📖 문제

level3 섬 연결하기

✏️ 나의 풀이

섬 연결하기 문제는 MST를 구하는 문제로, 크루스칼 알고리즘을 이용해 풀었다.

크루스칼 알고리즘

크루스칼 알고리즘은 간선의 가중치 중 가장 적은 가중치를 선택해나가는 방식이다.

계속해서 가장 적은 가중치를 선택하다가 만일 노드들이 순환을 이루게 되면 안되기에 순환을 이루는지 판별하는 로직이 필요하다.

무제 001

위와 같은 가중치가 있는 양방향 그래프가 있다고 가정하다.

무제 002

여기서 가장 가중치가 적은 1번 노드와 2번 노드를 잇는 간선을 선택한다.

무제 003

그 다음 가중치가 적은 1번 노드와 4번 노드를 잇는 간선을 선택한다.

무제 004

다음으로 가중치가 적은 2번 노드와 4번 노드를 잇는 간선을 선택할려하지만,
해당 간선을 선택하면 순환을 이루게 되어 MST에 부합하지 않게 된다.
그러므로 해당 간선을 선택하지 않는다.

무제 005

마지막으로 가중치가 적은 1번 노드와 3번 노드를 잇는 간선을 선택한다.

코드 설명

function solution(n, costs) {
    var answer = 0;
    let edge = 0;
    const cycleTable = new Array(n).fill(0).map((_, index)=>index);
}

우선, 서로 순환하는지 판별하기 위해 union find 알고리즘에 사용할 cycleTable 배열을 선언해준다.
배열의 각각 원소는 인덱스를 값으로 갖고 있는다.

function solution(n, costs) {
    ...
    const find = (a) => {
        if(cycleTable[a] === a) return a;
        return cycleTable[a] = find(cycleTable[a]);
    }
    const unionParent = (a, b) => {
        const [n1, n2] = [find(a), find(b)];
        if(n1 < n2) cycleTable[n2] = n1;
        else cycleTable[n1] = n2;
    }
    const isSameParent = (a, b) => {
            const [n1, n2] = [find(a), find(b)];
            return n1 === n2;
    }
}

find(x): x가 속한 집합의 대표값을 반환하는 함수이다.
unionParent(x, y): x가 속한 집합과 y가 속한 집합을 합치는 함수이다.
isSameParent(x, y): x, y가 같은 집합에 속해있는지 판별하는 함수이다.

function solution(n, costs) {
    ...
    costs.sort((a, b) => a[2] - b[2]);
    for(const cost of costs){
        const c = cost[2];
        const [s, e] = [cost[0], cost[1]].sort((a, b)=> a - b)
        if(isSameParent(s, e)) continue;
        answer += c;
        unionParent(s, e);
        edge += 1;
        if(edge === n-1) break;
    }
    return answer;
}

매개변수인 costs로 반복문을 돌리기 전 costs를 가중치 기준으로 오름차순으로 정렬해준다.
costs로 반복문을 돌리면서 두 노드가 같은 집합에 속해 있는지 판별한다.
- 만일 두 노드가 같은 집합에 속해있으면 순환을 이룰수 있으므로 continue문을 통해 다음으로 넘어간다.
같은 집합에 속해있지 않으면 answer에 가중치를 더해준다.
unionParent 함수를 통해 두 노드를 같은 집합에 속하게 한다.
MST는 간선이 노드 개수 - 1 이므로 현재 간선의 길이가 노드개수 - 1 과 부합하면 더이상 반복문을 돌릴 이유가 없기에 반복문을 중지시킨다.

👩‍💻 코드

function solution(n, costs) {
    var answer = 0;
    let edge = 0;
    const cycleTable = new Array(n).fill(0).map((_, index)=>index);
    
    const find = (a) => {
        if(cycleTable[a] === a) return a;
        return cycleTable[a] = find(cycleTable[a]);
    }
    const unionParent = (a, b) => {
        const [n1, n2] = [find(a), find(b)];
        if(n1 < n2) cycleTable[n2] = n1;
        else cycleTable[n1] = n2;
    }
    const isSameParent = (a, b) => {
        const [n1, n2] = [find(a), find(b)];
        return n1 === n2;
    }
    costs.sort((a, b) => a[2] - b[2]);
    for(const cost of costs){
        const c = cost[2];
        const [s, e] = [cost[0], cost[1]].sort((a, b)=> a - b)
        if(isSameParent(s, e)) continue;
        answer += c;
        unionParent(s, e);
        edge += 1;
        if(edge === n-1) break;
    }
    
    return answer;
}

YUN SEO