[프로그래머스] 지형 이동

사용 언어: Kotlin

 

문제

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

프로그래머스

\

각 배열의 숫자가 각 칸의 높이이다. height가 주어지면, 인접한 칸으로 height 이하만큼의 높이차가 나면 이동할 수 있다.

height 초과의 높이차가 나면, 비용(사다리)을 지불해 넘어갈수 있다. 이때, 모든 칸을 이동할 수 있도록 했을 때의 최소 비용을 return한다.  

제한사항

land[a][b] = (a,b) 칸의 높이

4 <= land의 길이 = land[i]의 길이 <= 300

1 <= land[a][b] <= 10000

height = 비용 없이 이동할 수 있는 높이차

1 <= height <= 10000

풀이

1. 비용 없이 이동할 수 있는 칸을 묶어 하나의 노드로 만든다. (예제 이미지에서 각각 노란색, 파란색, 빨간색으로 묶은 것처럼)
2. 각 노드에서 이동할 수 있는 노드와, 그 최소 비용을 구한다.
3. kruskal 알고리즘을 이용해 모든 노드를 연결하는 최소 비용을 구한다.

코드

처음엔 그룹을 하나의 노드로 만드는 코드를 DFS로 구현했더니, 정확성 테스트 24번이 런타임 에러가 났다.

BFS 코드로 바꾸니, 오류없이 정답처리 되었다.

fun solution(landHeightMap: Array<IntArray>, height: Int): Int {
    val landGroupMap = Array(landHeightMap.size) { Array(landHeightMap.size){0}.toIntArray() }
    val edgeMap = mutableMapOf<Pair<Int, Int>, Int>()
    val queue = ArrayDeque<Pair<Position?, Int>>()
    var groupCount = 0
    for(y in landHeightMap.indices) {
        for(x in landHeightMap.indices) {
            if(landGroupMap[y][x]==0) {
                groupCount++
                queue.add(Position(x,y,landHeightMap.size-1) to -1)
                while(queue.isNotEmpty()) {
                    val pair = queue.removeFirst()
                    makeGroupByBfs(landHeightMap, landGroupMap, edgeMap, queue, pair.first, groupCount, height, pair.second)
                }
            }
        }
    }
    val sortedEdgeList = edgeMap.map {
        Edge(it.key.first, it.key.second, it.value)
    }.sortedBy { it.cost }

    return kruskal(sortedEdgeList, groupCount)
}

class Edge(
    val from: Int,
    val to: Int,
    val cost: Int
)

class Position(
    val x: Int,
    val y: Int,
    val maxX: Int,
    val maxY: Int = maxX
) {
    fun up() = if(y==0) null else Position(x, y-1, maxX, maxY)
    fun down() = if(y==maxY) null else Position(x, y+1, maxX, maxY)
    fun left() = if(x==0) null else Position(x-1, y, maxX, maxY)
    fun right() = if(x==maxX) null else Position(x+1, y, maxX, maxY)
}

fun Array<IntArray>.findByPosition(position: Position) = this[position.y][position.x]

fun makeGroupByBfs(landHeightMap: Array<IntArray>, landGroupMap: Array<IntArray>, edgeMap: MutableMap<Pair<Int,Int>,Int>, queue: ArrayDeque<Pair<Position?, Int>>, position: Position?, groupName: Int, maxHeight: Int, befHeight: Int) {
    if(position == null) return
    val currentGroupName = landGroupMap.findByPosition(position)
    val currentHeight = landHeightMap.findByPosition(position)
    if(currentGroupName!=0) {
        if(currentGroupName > groupName) {
            edgeMap[groupName to currentGroupName] = min(abs(befHeight - currentHeight), edgeMap[groupName to currentGroupName] ?: Int.MAX_VALUE)
        } else if(currentGroupName < groupName) {
            edgeMap[currentGroupName to groupName] = min(abs(befHeight - currentHeight), edgeMap[currentGroupName to groupName] ?: Int.MAX_VALUE)
        }
        return
    }
    if(abs(befHeight - currentHeight) > maxHeight && befHeight != -1) return // height차이로 갈수없는곳

    landGroupMap[position.y][position.x] = groupName

    queue.add(position.up() to currentHeight)
    queue.add(position.down() to currentHeight)
    queue.add(position.left() to currentHeight)
    queue.add(position.right() to currentHeight)
}

fun kruskal(edgeList: List<Edge>, groupCount: Int): Int {
    val union = IntArray(groupCount+1) {it}
    var result = 0
    edgeList.forEach {
        if(!findParent(union, it.from, it.to)){
            result += it.cost
            unionParent(union, it.from, it.to)
        }
    }
    return result
}

fun unionParent(union: IntArray, a: Int, b: Int) {
    val aParent = getParent(union, a)
    val bParent = getParent(union, b)
    if(aParent < bParent) union[bParent] = aParent
    else union[aParent] = bParent
}

fun findParent(union: IntArray, a: Int, b: Int): Boolean {
    return getParent(union, a) == getParent(union, b)
}

fun getParent(union: IntArray, a: Int): Int {
    val parent = union[a]
    if(parent == a) return parent
    val root = getParent(union, parent)
    union[a] = root
    return root
}