프로그래머스 탐욕법(Greedy) 섬 연결하기 with Kotlin

프로그래머스 탐욕법 섬 연결하기 문제입니다.

IntelliJ에서의 풀이입니다.

val costs: Array<IntArray> = arrayOf(
    intArrayOf(0, 1, 5), intArrayOf(0, 3, 2), intArrayOf(0, 4, 3), intArrayOf(2, 5, 3),
    intArrayOf(1, 4, 1), intArrayOf(3, 4, 10), intArrayOf(1, 2, 2), intArrayOf(4, 5, 4)
)
val n = 6 // 11
val costs2: Array<IntArray> = arrayOf(
    intArrayOf(0, 1, 5), intArrayOf(1, 2, 3), intArrayOf(2, 3, 3), intArrayOf(3, 1, 2),
    intArrayOf(3, 0, 4)
)
val n2 = 4 // 9
val costs3: Array<IntArray> = arrayOf(
    intArrayOf(0, 1, 1), intArrayOf(0, 2, 2), intArrayOf(1, 2, 5), intArrayOf(1, 3, 3),
    intArrayOf(2, 3, 8), intArrayOf(3, 4, 1)
)
val n3 = 5 //7
val costs4: Array<IntArray> = arrayOf(
    intArrayOf(0, 1, 1), intArrayOf(3, 4, 1), intArrayOf(1, 2, 2), intArrayOf(2, 3, 4)
)
val n4 = 5 // 8

fun solution(n: Int, costs: Array<IntArray>): Int {
    val sortedCosts = costs.sortedBy { it[2] }
    // weight가 작은 것부터 ASC sorted, 그냥 작은 것부터 추가합니다..
    val visited = mutableSetOf(sortedCosts[0][0])
    // 가장 작은 weight를 가진 간선의 섬 중 하나를 방문한 상태로 시작합니다.
    var answer = 0
    while (visited.size < n) {
        for ((a: Int, b: Int, c: Int) in sortedCosts) {
            if (visited.contains(a) or visited.contains(b)) {
                // 방문 가능한 섬만 방문합니다.
                if (visited.contains(a) and visited.contains(b)) {
                    continue
                    // 이미 방문한 섬 2 곳이기 떄문에 pass 합니다.
                }
                visited.add(a)
                visited.add(b)
                answer += c
                break
                //방문한 섬 목록이 갱신되었기 때문에 break
            }
        }
    }
    return answer
}


fun main() {
    println(solution(n, costs)) // 11 // 0, 1 (5) // 0, 3 (2) // 1, 4 (1) // 2, 5 (3)
    println(solution(n2, costs2)) // 9 // 0, 3 (4) // 1, 3 (2) // 1, 2 (3)
    println(solution(n3, costs3)) // 7 // 0, 1 (1) // 0, 2 (2) // 1, 3 (3) // 3, 4 (1)
    println(solution(n4, costs4)) // 8 // 0, 1 (1) // 1, 2 (2) // 2, 3 (4) // 3, 4 (1)
}

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

코딩테스트 연습 - 섬 연결하기