[프로그래머스] Lv3. 섬 연결하기 Javascript 풀이 (feat. MST)

0. 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

프로그래머스 Lv3. 섬 연결하기 

토요일에 치는 코딩테스트가 Javascript로 쳐야 해서 Javascript도 알고리즘을 연습하다가 풀어본 문제이다.

Java로 배웠던 MST 개념을 다시 복습하며 Javascript로도 구현해보았다.

---

1. MST란?

MST(Minimum Spanning Tree, 최소 신장 트리)는 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 신장 트리를 의미한다.

여기서 무향 그래프란 사이클이 없는 그래프를 의미하고, 신장 트리는 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리를 의미한다 (➡️ 모든 정점이 연결 되어 있다)  

 

1) MST의 특징

즉, MST의 특징은 다음과 같다.

 

1. 간선의 가중치의 합이 최소

2. n개의 정점을 가지는 그래프에서 n-1개의 간선을 가진다

3. 사이클이 포함되지 않는다

 

2) MST 구현 방법

간선 중심인지, 정점 중심인지에 따라 Kruskal 알고리즘과 Prim 알고리즘(Prim 알고리즘은 나중에 기회가 되면 다뤄보겠다.)으로 나뉜다.

이번 문제에서는 Kruskal 알고리즘을 사용했다.

 

Kruskal 알고리즘

Kruskal 알고리즘은 그리디 알고리즘으로 MST를 찾는 알고리즘이다.

 

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 

2. 가중치가 가장 낮은 간선부터 선택하며 트리를 증가시킨다. (사이클이 존재하면 남아있는 간선 중 다음으로 낮은 가중치를 선택한다.) 

3. n-1개의 간선이 될 때까지 반복한다.

 

알고리즘 구현을 위해 서로소 집합개념이 사용된다.

 

- MakeSet(): 크기가 1인 서로소 집합을 생성하는 함수 (모든 정점을 크기가 1인 트리로 생성한다 = 간선을 아무것도 선택하지 않은 상황)

- Union(a, b): a가 속한 집합 ∪ b가 속한 집합 (가중치가 낮은 두 정점 합치기) 

- Find(a): a가 속한 집합의 대표자 찾기 (같은 트리인지 확인 ➡️ 같은 트리이면 사이클 발생!)

   Find 함수를 "경로 압축"이라고 하기도 한다.

 

Javascript로 구현해보기

1. 정렬

costs.sort((a, b) => a[2] - b[2]);

costs 배열은 "섬 연결하기" 문제에서 사용된 배열이다. 최소 비용(cost)을 찾아야 하므로 2번째 인자인 비용 순으로 오름차순 정렬 했다.

 

2. MakeSet (초기화)

const parent = Array.from({ length: n }, (_, idx) => idx);

• 여기서 parent 배열은 부모 노드를 담은 배열이다. 만약 parent[4] = 3이라면 4의 부모는 3으로 해석할 수 있다.
• 위의 코드를 실행하면 parent 배열은 [0, 1, 2, 3, 4, .., n]로 초기화 된다.

 

3. Find 함수 (경로 압축)

function find(x) {
	if(parent[x] != x) parent[x] = find(parent[x]);
	return parent[x]; 
}

• 재귀를 사용해서 부모를 찾아간다.

 

4. Union 함수 (루트 연결)

function union(a, b) {
	const rootA = find(a);
	const rootB = find(b);
    
	if(rootA < rootB) parent[rootB] = parent[rootA];
	else parent[rootA] = parent[rootB];
}

 

5. 간선 선택 반복

let totalCost = 0;
let edgeCount = 0;

for (const [a, b, cost] of costs) {
	if(find(a) != find(b)) {
    	union(a, b);
        totalCost += cost;
        edgeCount++;
        if(edgeCount === n-1) break;
    }
}

return totalCount

 

---

2. 문제 풀이

위와 같은 과정을 거쳐 풀어낸 정답 코드는 아래와 같다.

 

function solution(n, costs) {    
    let totalCost = 0;
    let edgeCount = 0;
    
    costs.sort((a, b) => a[2] - b[2]);
    
    const parent = Array.from({length: n}, (_, idx) => idx);
    
    function find(x) {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    } 

    function union(a, b){
        const rootA = find(a);
        const rootB = find(b);

        if(rootA < rootB) parent[rootB] = rootA;
        else parent[rootA] = rootB;
    }

    
    for (const [a, b, cost] of costs) {
        if (find(a) != find(b)) {
            union(a, b);
            totalCost += cost;
            edgeCount++;
            if(edgeCount === n-1) break;
        }
    }
    
    return totalCost
}

 

 

+ 추가로 BFS와 MST로 풀 수 있는 문제

https://school.programmers.co.kr/learn/courses/30/lessons/62050

프로그래머스