Programmers 62050 - 지형 이동

코딩테스트 연습 - 지형 이동 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

각 칸에는 높이가 적혀있고 이동하려면 칸 사이 높이차가 height 이하여야 한다.

height보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있다.

사다리 설치 비용은 높이차만큼 들어간다.

최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하게 하라.

시작점 위치는 중요하지 않다. 어차피 모든 점을 도달하려면 어느 점에서 시작하던 상관없다.

현재 위치에서 이동 위치는 이동 가능한 지점과 이동 불가능한 지점으로 나누어진다.

이동 가능한 위치는 그냥 이동하면 된다. 이제 이동 불가능한 지점을 어떻게 다룰지 생각해야 한다.

현재 탐색 가능 범위를 탐색하면서 사다리를 설치해야 하는 위치와 비용을 저장한다.

그중 가장 적은 비용을 꺼내 사다리를 설치하고 그 지점부터 탐색을 다시 시작한다.

지속적으로 사다리 설치 후보를 추가해 가면서 모든 지점이 탐색될 때까지 탐색한다.

1. (0,0)부터 시작해서 탐색을 진행한다. 이 과정은 BFS를 통해 탐색을 한다.
2. 사다리를 설치해야 하는 지점이 있다면 PQ에 좌표와 비용을 추가한다.
3. 탐색 가능한 범위를 탐색한 후 모든 지점이 탐색되지 않았다면 사다리를 하나 꺼내서 설치한다.
4. 만약 사다리를 설치한 위치가 이미 방문된 곳이라면 다음 사다리를 꺼낸다.
5. 이 과정은 모든 지점 탐색이 완료될 때까지 반복한다.

import java.util.*;

class Solution {
    static class Point {
        int r;
        int c;
        int cost;
        
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
        public Point(int r, int c, int cost) {
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
    }
    
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int solution(int[][] land, int height) {
        int N = land.length;
        boolean[][] visited = new boolean[N][N];
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.cost));
        pq.add(new Point(0, 0));
        int visitCount = N * N;
        int totalCost = 0;
        
        while (true) {
            // 아직 모든 지점을 방문하지 않음.
            Point start = null;
            while (!pq.isEmpty()) {
                start = pq.poll();
                if (!visited[start.r][start.c]) break; 
            }
            
            Queue<Point> q = new LinkedList<>();
            q.add(start);
            visited[start.r][start.c] = true;
            totalCost += start.cost;
            visitCount--;
            
            while (!q.isEmpty()) {
                Point curr = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = curr.r + DIRECTION[d][0];
                    int nc = curr.c + DIRECTION[d][1];
                    
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc]) continue;
                    
                    int gap = Math.abs(land[nr][nc] - land[curr.r][curr.c]);
                    if (gap <= height) {
                        q.add(new Point(nr, nc));
                        visited[nr][nc] = true;
                        visitCount--;
                    } else {
                        pq.add(new Point(nr, nc, gap));
                    }
                }
            }
            
            if (visitCount == 0) {
                return totalCost;
            }
        }
    }
    
}