섬 연결하기 (level 3)

원용현·2022년 10월 5일

알고리즘

프로그래머스

목록 보기

27/49

링크

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

문제

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의 비용이 주어지지 않는다.
모든 섬 사이의 다리 건설 비용이 주어지지 않는다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 본다.
연결할 수 없는 섬은 주어지지 않는다.

문제 풀이

각 섬끼리 다리를 건설할 때 드는 비용이 주어진다면 위의 사진과 같이 다리를 건설하면 가장 최소 비용이 나온다.

이 문제는 크루스칼 알고리즘과 그리드 알고리즘, Union-Find 알고리즘을 이해해야 풀이가 가능하다.

각 알고리즘에 대해서 링크를 남기니 먼저 읽어보고 오면 문제 풀이가 가능할 것이다.

그리드 알고리즘
Union-Find 알고리즘
크루스칼 알고리즘

코드

function solution(n, costs) {
    let cost = 0
    let parent = new Array(n).fill(0)
    parent.map((el, idx) => parent[idx] = idx)
    costs.sort((a, b) => a[2] - b[2])
    
    costs.map((el) => {
        if(!findParent(parent, el[0], el[1])) {
            cost += el[2]
            union(parent, el[0], el[1])
        }
        console.log(el, parent, cost)
    })
    
    return cost
}

const union = (parent, x, y) => {
    const node1 = getParent(parent, x)
    const node2 = getParent(parent, y)
    
    if(node1 < node2) parent[node2] = node1
    else parent[node1] = node2
}

const findParent = (parent, x, y) => {
    const node1 = getParent(parent, x)
    const node2 = getParent(parent, y)
    
    if(node1 === node2) return true
    else return false
}

const getParent = (parent, x) => {
    if(parent[x] === x) return x
    return getParent(parent, parent[x])
}