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

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

지형 이동

문제 설명

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

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

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

입출력및 제한사항

입출력 예에 대한 설명

입출력 예 #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로 탐색을 해야겠다고 생각했다. 탐색을 하면서 groupCnt로 몇번 그룹인지 visited배열에 저장해준다.
그 다음은 맵을 사용하여 그룹간의 비용을 최소값으로 갱신해가며 저장한다.
그러면 그룹간의 최소비용을 모두 알고 있기 때문에 최소 신장트리를 구하면 된다.
마침 크루스칼 알고리즘으로 풀었던 문제가 있어서 참고했다. 섬 연결하기

시간 초과)
첫 제출시 24,25번이 시간초과가 났다. return을 찍어보니까 그룹화를 하다가 시간초과가 발생했다.
보니까 큐로 상하좌우를 탐색할때 해당 블럭을 큐에 넣기전에 방문처리를 해주지 않아서였다.
당연하게 큐에 넣을때 해당 포지션을 미리 방문했다고 처리를 해줘야합니다.
1 2
3 4 이 있다면 1부터 시작하면 1에서 2,3을 큐에 추가합니다.
그 다음 2가 4를 추가하고, 3이 4를 또 추가하는 문제가 발생합니다.
아직 BFS관련 문제를 많이 풀어보지 않아서 헷갈렸던거 같다..

코드

import java.util.*
import kotlin.math.*

data class Position(var x : Int, var y : Int)
class Solution {    // 😃😊😉
    fun solution(land: Array<IntArray>, height: Int): Int {
        val visited = Array(land.size){IntArray(land.size)}
        val map = hashMapOf<String,Int>()
        val queue : Queue<Position> = LinkedList()
        var groupCnt = 0

        for (i in land.indices){
            for (j in land.indices){
                // 그룹화
                if (visited[i][j] == 0){
                    groupCnt++
                    queue.offer(Position(i,j))
                    visited[i][j] = groupCnt
                    while (queue.isNotEmpty()){
                        val x = queue.poll()
                        //상
                        if(x.x-1 != -1 && visited[x.x-1][x.y]==0
                                && abs(land[x.x][x.y]-land[x.x -1][x.y]) <= height){
                            visited[x.x-1][x.y] = groupCnt      // 미리 visited를 체크해준다.   
                            //미리 안하면 중복으로 될 수 있어서 시간초과 발생.
                            queue.offer(Position(x.x-1, x.y))
                        }
                        //하
                        if(x.x+1 < land.size && visited[x.x+1][x.y]==0
                                && abs(land[x.x][x.y]-land[x.x + 1][x.y]) <= height){
                            visited[x.x+1][x.y] = groupCnt
                            queue.offer(Position(x.x+1, x.y))
                        }
                        //좌
                        if(x.y-1 != -1 && visited[x.x][x.y-1]==0
                                && abs(land[x.x][x.y]-land[x.x][x.y-1]) <= height){
                            visited[x.x][x.y-1] = groupCnt
                            queue.offer(Position(x.x, x.y-1))
                        }
                        //우
                        if(x.y+1 < land.size && visited[x.x][x.y+1]==0
                                && abs(land[x.x][x.y]-land[x.x][x.y+1]) <= height){
                            visited[x.x][x.y+1] = groupCnt
                            queue.offer(Position(x.x, x.y+1))
                        }
                    }
                }
            }
        }

        // 그룹간의 비용 구하기. 아래랑 오른쪽만 탐색하면 됨
        for (i in land.indices){
            for (j in land.indices){
                if (i+1 < land.size && visited[i][j] != visited[i+1][j]){
                    val x = min(visited[i][j],visited[i+1][j])
                    val y = max(visited[i][j],visited[i+1][j])

                    map.computeIfPresent("$x $y") { s, _ -> min(map[s]!!, abs(land[i][j] - land[i + 1][j])) }
                    map.computeIfAbsent("$x $y") { abs(land[i][j] - land[i + 1][j]) }

                }
                if (j+1 < land.size && visited[i][j] != visited[i][j+1]){
                    val x = min(visited[i][j],visited[i][j+1])
                    val y = max(visited[i][j],visited[i][j+1])

                    map.computeIfPresent("$x $y") { s,_ -> min(map[s]!!, abs(land[i][j] - land[i][j+1])) }
                    map.computeIfAbsent("$x $y") { abs(land[i][j] - land[i][j+1]) }
                }
            }
        }

        // 최소신장트리 크루스칼 알고리즘
        val kruskal = IntArray(groupCnt+1){it}
        val arr = map.toList().sortedBy { it.second }
        var answer = 0

        fun findParent(n: Int): Int {
            if (kruskal[n] == n)
                return n
            return findParent(kruskal[n])
        }
        fun hap(a: Int, b: Int) {
            val x = findParent(a)
            val y = findParent(b)
            if (x>y)    kruskal[x] = y
            else    kruskal[y] = x
        }
        var cnt = groupCnt
        for (x in arr) {
            val i = x.first.split(" ")
            if (findParent(i[0].toInt()) != findParent(i[1].toInt())) {
                hap(i[0].toInt(), i[1].toInt())
                answer += x.second
                if (cnt--==1)
                    break
            }
        }

        return answer
    }
}