[Lv3] 섬 연결하기 - python, kotlin

프로그래머스

문제 설명

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

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.

예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

제한 사항

1. 섬의 개수 n은 1 이상 100 이하입니다.

2. costs의 길이는 ((n-1)*n)/2이하입니다.

3. cost = [i, j, c] = i 섬과 j 섬을 연결하는 다리를 건설할 때 드는 비용 c

4. 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.

5. 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.

6. 연결할 수 없는 섬은 주어지지 않습니다.

 

풀이

문제를 읽어보면 어떠한 알고리즘을 사용할 수 있는지 알 수 있어요.

🌹 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소비용

바로! 크루스칼 알고리즘입니다! 😆

크루스칼 알고리즘은 Union&Find 알고리즘을 사용해서 최소 신장 트리를 만들어, 모든 정점을 연결하는데 필요한 최소 비용을 구할 때 사용할 수 있어요.

 

그럼 코드를 하나씩 생각해보면서 문제를 풀어보겠습니다. 🤗

1. costs 비용 정렬하기

먼저 가중치(cost)가 가장 적은 간선부터 순차적으로 탐색할 수 있도록 주어진 costs를 '다리를 건설할 때 드는 비용'에 따라 정렬하도록 하겠습니다.

python

costs.sort(key = lambda x : x[2])

kotlin

costs.sortBy { it[2] }

2. Union & Find

Union & Find 알고리즘에 필요한 코드는 3가지가 있어요,

• 특정 정점의 parent를 찾는 메서드 -> getParent(x)
• 두 그룹을 하나로 합치는 메서드 -> union(x, y)
• 두 정점이 같은 그룹에 포함되었는지 확인하는 메서드 -> find(x, y)

getParent(x)

def getParent(x):
	if parent[x] = x : return x
    parent[x] = getParent(parent[x])
    return parent[x]

private fun getParent(x: Int): Int =
	if (parent[x] == x) x
    else {
    	parent[x] = getParent(parent[x])
        parent[x]
    }

union(x, y)

def union(x, y):
	a = getParent(x)
    b = getParent(y)
    if a < b : parent[b] = a
    else: parent[a] = b

private fun union(x: Int, y: Int) {
	val a = getParent(x)
    val b = getParent(y)
    if (a < b) parent[a] = b else parent[b] = a
}

find(x, y)

def find(x, y):
	a = getParent(x)
    b = getParent(y)
    if a == b : return True
    return False

fun find(x: Int, y: Int): Boolean {
    val a = getParent(x)
    val b = getParent(y)
    return a == b
}

그러면 정렬된 costs와 Union & Find 메서드들을 사용한 크루스칼 알고리즘을 구현해보겠습니다.

 

코드

python

parent = []
def solution(n, costs):
    global parent
    answer = 0
    # Union & Find
    parent = [x for x in range(n)]
    # 가중치의 오름차순으로 정렬
    costs.sort(key = lambda x : x[2])
    
    for s, e, c in costs:
        if find(s,e): continue
        answer += c
        union(s,e)
    
    return answer

def getParent(x):
    global parent
    if parent[x] == x: return x
    parent[x] = getParent(parent[x])
    return parent[x]

def union(x, y):
    global parent
    a = getParent(x)
    b = getParent(y)
    if a < b: parent[b] = a
    else: parent[a] = b
    
def find(x, y):
    a = getParent(x)
    b = getParent(y)
    if a == b: return True
    return False

kotlin

class Solution {
    
    lateinit var parent: IntArray
    fun solution(n: Int, costs: Array<IntArray>): Int {
        var answer = 0

        parent = IntArray(n){ it }
        costs.sortBy { it[2] }

        costs.forEach { (s, e, cost) ->
            if (find(s, e).not()) {
                answer += cost
                union(s, e)
            }
        }

        return answer
    }

    private fun getParent(x: Int): Int =
        if (parent[x] == x) x
        else {
            parent[x] = getParent(parent[x])
            parent[x]
        }
    
    fun union(x: Int, y: Int) {
        val a = getParent(x)
        val b = getParent(y)
        if (a < b) parent[a] = b else parent[b] = a
    }
    
    fun find(x: Int, y: Int): Boolean {
        val a = getParent(x)
        val b = getParent(y)
        return a == b
    }
}