문제

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

풀이

그래프 탐색을 이용해 문제를 풀었다.

고저 차가 height이하 인 블럭 간 이동에는 사다리가 필요 없다. 예시 모형에는 이동에 사다리가 필요 없는 블럭 그룹은 같은 색으로 칠해져 있다. 블럭 그룹 사이에 놓아야 하는 사다리들의 최소 비용 합이 구하고자 하는 정답이다.

풀이 방식은 사다리 없이 탐색 가능한 모든 블럭 탐색 -> 사다리로 접근 가능 한 블럭 중 가장 비용이 적게 필요한 블럭 탐색의 두 과정을 단순 반복한다. 그래프 탐색은 bfs로, 가장 비용이 적은 사다리를 찾는 것은 우선순위 큐를 이용하여 구현하였다.

아무 블럭에서나 출발할 수 있는데 어느 블럭에서 출발하던 결과는 같다.

코드

import java.util.*;

class Solution {
    
    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    static int n,m,h,board[][];
    
    public int solution(int[][] land, int height) {
        
        n = land.length;
        m = land[0].length;
        h = height;
        board = land;
        
        return bfs();
    }
    
    static int bfs(){
        boolean been[][] = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b) -> a[2] - b[2]);
        pq.add(new int[]{0, 0, 0});
                
        int cost = 0;
        
        while(!pq.isEmpty()){
            int[] pp = pq.poll();
            if(been[pp[1]][pp[0]]){
                continue;
            }
            
            cost += pp[2];
            queue.add(new int[]{pp[0],pp[1]});
            been[pp[1]][pp[0]] = true;

            while(!queue.isEmpty()){
                int p[] = queue.poll();
                
                for(int i = 0; i < 4; i++){
                    int nx = p[0] + dx[i];
                    int ny = p[1] + dy[i];
                
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n || been[ny][nx] ){
                        continue;
                    }
                
                    int dif = Math.abs(board[p[1]][p[0]] - board[ny][nx]);
                    if(dif > h){
                        pq.add(new int[]{nx,ny, dif});
                        continue;
                    }
                
                    been[ny][nx] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        
        return cost;
    }
}

---

이 벨로그의 첫 글인데.. 잘 모르겠네요.