[kotlin/프로그래머스/Summer&Winter Coding(2019)] 지형 이동

https://programmers.co.kr/learn/courses/30/lessons/62050?language=kotlin 

코딩테스트 연습 - 지형 이동

 

문제

 N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

 

 이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다.

 

 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

 

 각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

---

입출력 예

land                                                                                                                               height  result

[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]	3	15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

입출력 예 설명

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

입출력 예 #2

각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.

 

해결 과정

BFS로 이동이 가능한 그룹끼리 묶는 것 까지는 성공. 이 후 사다리 놓을 때 그룹별 BFS로 돌아다니면서 높이 비교하고 사다리 놓으면 되겠다 싶었는데 시간도 오래걸리고, 코드도 복잡해져서 실패.

 

• BFS 사용 - 그룹 설정 + 각 그룹을 인덱스를 키로 하는 해쉬맵(hashMap)에 해당 그룹의 좌표 추가.
  
  
• List<Edge> 만들기 - 해쉬맵의 key(=그룹)별로 좌표들을 움직여가면서 이동할 수 없는 좌표(높이차)를 만나면 [해당 좌표와 현재 좌표]를 [두 개의 노드]로 설정 하고 [높이 차이]를 [간선의 가중치]로 설정하여 Edge 클래스에 저장.
  
  이 후 해당 Edge를 List<Edge>에 추가시킴
  
  
• "유니온 파인드 - 크루스컬"  사용 : List<Edge> 를 가중치 기준 오름차순 정렬한 뒤, 첫번째 원소부터 참조. 크루스컬 알고리즘 사용하여 사다리 설치
  
  

소스 코드

package programmers

import test01.UnionFind
import kotlin.math.absoluteValue

typealias P1 = Pair<Int,Int>

class SolutionInstallLadder {
    //오른쪽,왼쪽,아래쪽,위쪽
    val move = arrayOf(P1(0,1), P1(0,-1), P1(1,0), P1(-1,0))
    var visit : Array<Array<Int>> = arrayOf()

    //groupNumber가 key가 되고, mutableList에 좌표를 집어넣는 형식. -> 시간초과 해결하기 위해서
    val hashMap : HashMap<Int,MutableList<P1>> = hashMapOf()

    var N = 0
    var ladder = 0

    fun P1.plus(_p:P1) : P1 = P1(this.first + _p.first, this.second + _p.second)


    fun solution(land: Array<IntArray>, height: Int): Int {
        N = land.size
        val graph = mutableListOf<Edge>()

        visit = Array(N){Array(N){0}}

        var groupNum = 1
        for(i in 0 until N) {
            for(j in 0 until N) {
                if(visit[i][j]>0) continue
                BFS(land,height, P1(i,j), groupNum)
                groupNum++
            }

        }
        
        ladder = groupNum-1

        for(i in 1..ladder) {
            findLadder(land, graph ,i)
        }

        graph.sort()
        
        return Kruskal_custom(graph,N)

    }

    fun BFS(land:Array<IntArray>, height: Int, start:P1, groupNum:Int) {
        val q = ArrayList<P1>()
        var s = start
        var (x,y) = s

        visit[x][y] = groupNum
        //println("BFS X : $x, Y : $y")
        hashMap.put(groupNum, mutableListOf<P1>().also { it.add(s) })
        q.add(s)

        while(!q.isEmpty()) {
            s = q[0]
            var (s_x, s_y) = s

            q.removeAt(0)

            for(i in 0 until 4) {
                val next = s.plus(move[i])
                val (n_x, n_y) = next

                if(!isLand(n_x,n_y)) continue

                //val interval = (land[s_x][s_y] - land[n_x][n_y]).absoluteValue
                val interval = Math.abs(land[s_x][s_y] - land[n_x][n_y])

                if(visit[n_x][n_y] > 0 || interval > height) continue

                visit[n_x][n_y] = groupNum
                q.add(next)

                hashMap[groupNum]?.add(next) ?: hashMap.put(groupNum, mutableListOf<P1>().also { it.add(next)})
            }
        }
    }

    fun findLadder(land:Array<IntArray>, graph: MutableList<Edge>, groupNum: Int)  {

        val groupVisit = hashMap[groupNum] ?: return

        //println(groupVisit)

        groupVisit.forEach { s->
            val (s_x,s_y) = s
            val s_g = groupNum

            for(i in 0 until 4) {
                val n = s.plus(move[i])
                val (n_x, n_y) = n


                if(!isLand(n_x,n_y) || visit[n_x][n_y] <= s_g) continue

                //nextGroup
                val n_g = visit[n_x][n_y]
                val dist = Math.abs(land[s_x][s_y] - land[n_x][n_y])

                graph.add(Edge(s_g,n_g,dist))
            }
        }
    }

    fun Kruskal_custom(graph:List<Edge>, size:Int) : Int {
        var sum = 0
        val n = size * size
        val rootParent = Array(n+1){0}
        val groupVisit = Array(n+1){false}

        for(i in 1..n) rootParent[i] = i

        val uf = UnionFind()

        for(i in 0 until graph.size) {
            val x = graph[i].node[0]
            val y = graph[i].node[1]
            val dist = graph[i].dist

            if(!uf.findParent(rootParent,x,y)) {
                sum += dist
                uf.unionParent(rootParent,x,y)
            }
        }

        return sum
    }

    fun isLand(x:Int, y:Int) : Boolean = !(x<0 || y<0 || x>=N || y>=N)


}

class Edge(a:Int, b:Int, _dist:Int) : Comparable<Edge> {
    val node = Array(2){0}
    var dist = 0

    init {
        node[0] = a
        node[1] = b
        dist = _dist
    }

    override fun compareTo(other: Edge): Int = this.dist - other.dist
}

fun main() {
    val solution = SolutionInstallLadder()
    val arr = arrayOf(intArrayOf(1,4,8,10), intArrayOf(5,5,5,5), intArrayOf(10,10,10,10), intArrayOf(10,10,10,20))
    val arr2 = arrayOf(intArrayOf(10,11,10,11), intArrayOf(2,21,20,10), intArrayOf(1,20,21,11), intArrayOf(2,1,2,1))
    val height = 3

    println(solution.solution(arr2,1))
}


//노드 1, 2 사이에 수많은 WEIGHT를 가진 간선이 있다고 생각하고, 다 넣어버리자.
//그리고 그룹을 edge로 list에 add할 때 자신의 그룹번호보다는 낮은 그룹번호는 무시하도록. - 이미 이 전에 추가가 되었기 때문.