[ 프로그래머스 ] 섬 연결하기 (Kotlin )

📌 [ 프로그래머스 ] 섬 연결하기

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

 

📌 접근1( 통과 X )

1. 코스트가 낮은 순으로 정렬한다.

2. 코스트가 낮은순으로 순회하며 출발지 와 도착지 두개중에 한섬이라도 등록이 안되어 있는 지를 찾는다.

문제 상황

1.   모든 노드에 대한 연결을 보장할 수 없다.
2.   사이클에 대한 고려가 없다.

// 본방식은 통과지 못한 풀이입니다.

class Solution {
    fun solution(n: Int, costs: Array<IntArray>): Int {
        var answer = 0
        val restList = (0..n-1).toHashSet()

        costs.sortBy { it[2] }
        var flag = false

        costs.forEach{
            if(restList.contains(it[0]) || restList.contains(it[1])){
                if(!restList.contains(it[0]) && !restList.contains(it[1])){
                    flag =true
                }
                restList.remove(it[0])
                restList.remove(it[1])
                answer += it[2]
            }
            if(restList.isEmpty() && flag == true){
                return@forEach
            }
        }

        return answer
    }
}

 

 

📌 접근2 - 크루스칼 알고리즘

1. 코스트가 낮은 순으로 정렬한다.
2.  코스트가 낮은 순으로 순회하며 사이클이 생기지 않는다면 선을 연결한다.(노드를 추가한다.)
   1. 사이클에 대한 판단은 UnionFind 알고리즘을 사용한다.
   2. 시작한 도느와 도착 노드에 대해 부모가 같은지를 확인하는 작업으로 볼 수 있다.

 

 

결국 문제의 핵심은 두 가지로 볼 수 있겠다.

• 신장트리 및 크루스칼 알고리즘을 알고있는지
• UnionFind 의 Union 함수와 Find 함수를 작성할 수 있는지 

 

https://easycodediary.tistory.com/117

크루스칼 알고리즘

 

import kotlin.math.min


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

       costs.sortBy { it[2] }

        for (i in costs.indices) {
            if (findParent(parentList,costs[i][0]) != findParent(parentList, costs[i][1])) {

                answer += costs[i][2]

                // 이제 연결이 되었다면 같은 부모로 귀속
                unionParent(parentList,costs[i][0], costs[i][1])
            }
        }
        return answer
    }

    private fun findParent(parentList: IntArray ,idx: Int): Int {
        return if (parentList[idx] == idx) idx
        else findParent(parentList , parentList[idx])
    }

    private fun unionParent(parentList: IntArray, aNode: Int, bNode: Int) {
        val aParent = findParent(parentList, aNode)
        val bParent = findParent(parentList, bNode)
        val newParent = min(aParent,bParent)
        parentList[aParent] = newParent
        parentList[bParent] = newParent
    }
}