[LV3] 섬 연결하기

문제

 

풀이

항목이 '탐욕법'으로 되어 있어서, 처음에는 dfs를 통해 모든 경로를 다 탐색한 후 그 중 최소 거리를 찾으려 했다.

하지만 개같이 실패에 시간초과까지,..,.,,

결국 다른 방법을 사용해 보기로 했다.

 

내가 찾아본 방법은 '크루스칼 알고리즘'으로, 모든 정점을 연결 할 때, 최소의 비용을 찾는 알고리즘이라고 한다.

정확히 이 문제를 풀기에 적합한 알고리즘으로, 각 정점과 가중치가 주어졌을 때, 현재 정점이 연결 되어 있는지 아닌지를 파악하여 연결 되어있다면 패스, 안되어 있다면 가중치를 더하는 방식을 사용한다.

 

 위와 같은 그래프의 각 정점을 모두 이었을 때, 최소 가중치를 구하는 방법을 알아보자

먼저 가중치의 오름차순으로 정렬해 준다.

 

그 다음, 각 연결별로 순회하며 노드의 부모 노드들을 비교해 준다.

초기 노드들의 부모 노드들은 각각 자기 자신이며, 만약 두 정점의 부모 노드가 다를 경우, 둘중 작은 노드로 부모 노드를 변경해 준다.

이 과정은 '유니온 파인드 알고리즘'을 사용했다.

 

 

1 -> 3 노드는 각각 부모 노드가 1, 3으로 다르다. 따라서 3의 부모 노드를 더 작은 1로 바꾸어 준다.

이 과정을 거치면 1과 3은 같은 부모 노드 1을 갖게 된다.

 

 

그 다음 2 -> 3 노드를 비교해 보자.

2의 부모 노드는 2, 3의 부모 노드는 1이다. 두 노드의 부모 노드가 다르므로, 둘중 더 작은 부모 노드는 1이다.

따라서, 2의 부모 노드를 1로 바꿔준다.

 

 

세번째 1->2 노드이다. 

1과 2의 부모 노드는 1로 같으므로, 이 연결은 패스해 준다.

 

2->4 노드도 같은 방법으로 확인해 준다.

2의 부모 노드는 1, 4의 부모 노드는 4이므로, 더 작은 1로 바꿔 준다.

이 과정까지 마치면, 모든 노드의 부모 노드는 1이 된다.

즉, 모든 노드가 하나의 연결이 되었다는 말이다. 

가중치 순으로 정렬했기 때문에, 지금까지의 가중치의 합이 모든 노드를 잇는 최소 가중치 합이 된다.

 

굳이 마지막까지 해보자면, 3-> 4 노드에서 3의 부모노드와 4의 부모노드가 1로 같기 때문에 패스 해 주면 된다.

 

코드

//각 노드의 부모를 담을 객체
const parents = {}

function solution(n, costs) {
	//섬의 번호가 순차적으로 주어지지 않기 때문에, 최대 갯수인 100개 반복
    for(let i = 0; i < 100; i++){
        parents[i] = i
    }
    
    //가중치 순서대로 오름차순 정렬
    costs.sort((a,b) => a[2] - b[2])
    
    let ans = 0
    //시작 노드, 도착 노드, 가중치를 union 함수에 전달
    for(let [s, e, c] of costs){
    	//순회하는 시작, 도착 노드가 같은 부모를 가질 경우 0, 다른 부모를 가질 경우 가중치를 더함
        ans += union(s, e, c)   
    }
    return ans
}

//부모 노드를 찾는 함수
const getParent = (node) => {
	// 노드의 key값과 value가 같으면 => 가장 작은 번호의 노드이므로, 부모 노드가 된다 
    if(parents[node] === node){
        return node
    } else {
    //아닌 경우 재귀로 부모의 부모를 찾아감
        return getParent(parents[node])
    }
}

// 부모가 같은 노드를 합치는 과정
const union = (start, end, cost) => {
	//시작 노드의 부모 노드
    const startP = getParent(start)
    //도착 노드의 부모 노드
    const endP = getParent(end)
    
    //시작, 도착 노드의 부모 노드가 같다면, 이미 연결된 노드이므로 스킵
    if(startP === endP) return 0
    
    //다르다면, 둘 중 작은 노드를 부모 노드로 만듦
    if(startP > endP){
        parents[startP] = endP
    } else {
        parents[endP] = startP
    }
    //가중치를 리턴
    return cost
}