[프로그래머스/탐욕법(Greedy)/5] 섬 연결하기 (JS)

출처: 프로그래머스 코딩테스트 섬 연결하기 (Greedy) 5번째 문제
(https://programmers.co.kr/learn/courses/30/lessons/42861)

문제 설명

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

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

제한사항

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

풀이 방법

1. 간선의 사이클을 방지하기위해 합집합 배열인 union 배열을 생성
2. costs 배열을 비용을 기준으로 오름차순으로 정렬
3. costs 배열에 간선들을 순회하는 반복문을 돌린다.
   해당 반복문은 cnt라는 섬이 연결된 갯수를 이용하여 모든 섬이 연결되면 반복문이 종료된다.
   4.connect 함수를 이용해서 섬을 잇는다. 섬을 이었으면 union 배열에 합집합으로 추가한다.
4. connect 함수를 통해 섬이 연결되면 가중치를 answer에 더한다.
5. answer 변수를 반환한다.

소스 코드

function solution(n, costs) {
    if (n === 1) return 0

    let answer = 0
    const union = new Array(n).fill().map((el, idx) => idx)
    costs = costs.sort((a, b) => a[2] - b[2])

    for (let i = 0, cnt = 0; cnt < n - 1; i++) {
        if (!connect(union, costs[i])) continue
        answer += costs[i][2]
        cnt++
    }

    return answer
}

function connect(union, cost) {
    const parentA = findParent(union, cost[0])
    const parentB = findParent(union, cost[1])

    if (parentA === parentB) {
        return false
    }

    if (parentA > parentB) {
        union[parentA] = parentB
    } else {
        union[parentB] = parentA
    }

    return true
}

function findParent(union, idx) {
    const hasParent = union[idx] !== idx
    
    if (hasParent) {
        union[idx] = findParent(union, union[idx])
    }
    
    return union[idx]
}

후기

개인적으로 학부생때 다익스트라 알고리즘을 배울 때는 뭔가 감이 안왔는데 요번 문제를 통해서 확실하게 어떤 느낌인지 깨닫게 되었다. 좋은 예제인 것 같아 남에게 추천해줘도 될 것 같다.