문제출처: https://programmers.co.kr/learn/courses/30/lessons/62050

문제

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 이하인 자연수입니다.

풀이

BFS를 통해 먼저 사다리없이 이동 가능한 공간을 모두 탐색 후 사다리가 필요한 이동 공간으로 이동 후 다시 그곳에서부터 사다리 없이 이동 가능한 공간을 탐색하는 방법을 사용했다.

• 이동 가능한 공간의 좌표와 이동에 필요한 가격을 담고 있는 class Land를 만든다.
• Land는 PriorityQueue에 넣을 예정이기 때문에 Comparable 인터페이스를 implement 한다.
• Queue에 탐색할 첫번째 Land를 넣은 뒤 BFS를 통해 사다리 없이 이동 가능한 모든 공간을 탐색한다.
• 더 이상 사다리 없이 이동 가능한 공간이 없을때, PriorityQueue를 이용해서 사다리가 필요한 공간 중 가장 가격이 낮은 공간부터 Queue에 넣어준 뒤 그 공간부터 다시 BFS를 통해 사다리 없이 이동 가능한 모든 공간을 탐색한다.
• 반복한다 -> 총 비용을 반환한다

코드

import java.util.*;

class Solution {
    //공간의 좌표와 전 공간에서 이동에 필요한 가격을 담은 클래스
    class Land implements Comparable<Land> {
        int row;
        int col;
        int cost;
        public Land(int row, int col, int cost) {
            this.row = row;
            this.col = col;
            this.cost = cost;
        }
        //PriorityQueue에 cost가 낮은 순으로 정열하기 위한 메소드
        @Override
        public int compareTo(Land l) {
            if (this.cost < l.cost) {
                return -1;
            }
            else if (this.cost > l.cost) {
                return 1;
            }
            return 0;
        }
    }
    public int solution(int[][] land, int height) {
        int answer = 0;
        int N = land.length;
        boolean[][] visited = new boolean[N][N];
        Queue<Land> landNoLadder = new LinkedList<Land>();
        PriorityQueue<Land> landNeedLadder = new PriorityQueue<Land>();
        landNoLadder.offer(new Land(0, 0, 0));
        
        while (!landNoLadder.isEmpty()){
            Land curr = landNoLadder.poll();
            if (!visited[curr.row][curr.col]) {
                visited[curr.row][curr.col] = true;
                answer += curr.cost;
                //check left
                if (curr.col > 0) {
                    //사다리없이 이동 가능한 경우
                    if (Math.abs(land[curr.row][curr.col] - land[curr.row][curr.col - 1]) <= height) { 
                        landNoLadder.offer(new Land(curr.row, curr.col - 1, 0));
                    } 
                    //이동에 사다리가 필요한 경우
                    else {
                        landNeedLadder.offer(new Land(curr.row, curr.col - 1, 
                                                      Math.abs(land[curr.row][curr.col] - land[curr.row][curr.col - 1])));
                    }
                }
                //check right
                if (curr.col < N - 1) {
                    //사다리없이 이동 가능한 경우
                    if (Math.abs(land[curr.row][curr.col] - land[curr.row][curr.col + 1]) <= height) { 
                        landNoLadder.offer(new Land(curr.row, curr.col + 1, 0));
                    } 
                    //이동에 사다리가 필요한 경우
                    else {
                        landNeedLadder.offer(new Land(curr.row, curr.col + 1, 
                                                      Math.abs(land[curr.row][curr.col] - land[curr.row][curr.col + 1])));
                    }
                }
                //check up
                if (curr.row > 0) {
                    //사다리없이 이동 가능한 경우
                    if (Math.abs(land[curr.row][curr.col] - land[curr.row - 1][curr.col]) <= height) { 
                        landNoLadder.offer(new Land(curr.row - 1, curr.col, 0));
                    } 
                    //이동에 사다리가 필요한 경우
                    else {
                        landNeedLadder.offer(new Land(curr.row - 1, curr.col, 
                                                      Math.abs(land[curr.row - 1][curr.col] - land[curr.row][curr.col])));
                    }
                }
                //check down
                if (curr.row < N - 1) {
                    //사다리없이 이동 가능한 경우
                    if (Math.abs(land[curr.row][curr.col] - land[curr.row + 1][curr.col]) <= height) { 
                        landNoLadder.offer(new Land(curr.row +1, curr.col, 0));
                    } 
                    //이동에 사다리가 필요한 경우
                    else {
                        landNeedLadder.offer(new Land(curr.row + 1, curr.col, 
                                                      Math.abs(land[curr.row + 1][curr.col] - land[curr.row][curr.col])));
                    }
                }
            }
            //더이상 사다리없이 이동 가능한 공간이 없을때 가장 낮은값으로 이동할 수 있는 공간을 추가한다
            if (landNoLadder.isEmpty()) {
                if (!landNeedLadder.isEmpty()) landNoLadder.offer(landNeedLadder.poll());
            }   
        }
        return answer;
    }
}