[프로그래머스] 지형 이동 - 자바 Java

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

프로그래머스

 

개념: bfs, 정렬

 

문제 설명

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

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

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

---

입출력 예

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

---

풀이

우선순위 큐를 통해 이동할 수 있는 다음 칸 중 비용이 가장 적은 칸부터 접근하도록 구현한다.

 

전체코드

import java.util.*;

class Solution {
    static int N, answer;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;
    static PriorityQueue<Node> pq = new PriorityQueue<>();

    static class Node implements Comparable<Node> {
        int x, y, cost;
        
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        // 비용 오름차순 정렬
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.cost, other.cost);
        }
    }

    public int solution(int[][] land, int height) {
        N = land.length;
        answer = 0;
        visited = new boolean[N][N];

        pq.offer(new Node(0, 0, 0));

        while (!pq.isEmpty()) {
            Node curr = pq.poll();  // 다음 칸 중 비용이 최소인 칸을 선택

            if (visited[curr.x][curr.y]) {
                continue;
            }

            visited[curr.x][curr.y] = true;
            answer += curr.cost;

            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    // 비용 처리
                    int heightDiff = Math.abs(land[nx][ny] - land[curr.x][curr.y]);
                    int newCost = heightDiff > height ? heightDiff : 0;
                    pq.offer(new Node(nx, ny, newCost));
                }
            }
        }
        
        return answer;
    }
}