[리트코드] 407. Trapping Rain Water 2 <Java>

문제

---

https://leetcode.com/problems/trapping-rain-water-ii/

Trapping Rain Water II - LeetCode

 

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

 

 

풀이

---

겉 테두리가 모두 현재의 위치보다 높은 높이로 둘러쌓인 공간을 구하는 문제다.

 

인접한 4개의 방향의 블럭을 방문하면서 높이 오름차순으로 정렬 된 우선순위큐 순서대로 방문을 했을 때,

현재 까지 방문한 노드중 최대 높이 보다 낮은 높이를 나중에 방문하게 되면

사방이 다 높은 높이로 둘러쌓인 구간임을 추측할 수 있다. 이를 이용해서 문제를 푼다.

 

알고리즘 순서

1. 왼쪽, 오른쪽 끝의 도형을 PriorityQueue에 넣어준다. (이 때, 높이 오름차순으로 정렬한다.)
2. PriorityQueue가 빌 때까지 반복문을 수행한다.
3. 현재까지의 최대 높이보다 현재블럭의 높이가 낮으면, 높이 차를 answer 값에 더해준다.
4. 최대높이 와 현재 높이 중 더 큰 값을 저장한다.
5. 인접한 4개의 방향(상, 하, 좌, 우)의 도형 중 아직 방문하지 않은 곳을 PriorityQueue에 넣어준다.
6. 2번 부터 다시 반복한다.

<전체코드>

class Solution {
    
    static int[][] direction = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public int trapRainWater(int[][] heightMap) {
        int n = heightMap.length;
        int m = heightMap[0].length;
        
        PriorityQueue<Node> pq  = new PriorityQueue<>();
        
        boolean[][] visited = new boolean[n][m];
        
        for(int i = 0 ; i < n ; i++){
            pq.add(new Node(i, 0, heightMap[i][0]));
            pq.add(new Node(i, m - 1, heightMap[i][m - 1]));
            
            visited[i][0] = true;
            visited[i][m - 1] = true;
        }
        
        for(int i = 0 ; i < m ; i++){
            pq.add(new Node(0, i, heightMap[0][i]));
            pq.add(new Node(n - 1, i, heightMap[n - 1][i]));
            
            visited[0][i] = true;
            visited[n -1][i] = true;            
        }
        
        int level = Integer.MIN_VALUE;
        int answer = 0;
        while(!pq.isEmpty()){
            
            Node top = pq.poll();
            int x = top.x;
            int y = top.y;
            int h = top.h;
            
            if(h < level){
                answer += (level - h);
            }
            
            level = Math.max(level, h);
            for(int i = 0 ; i < 4;  i++){
                int nx = x + direction[i][0];
                int ny = y + direction[i][1];
                
                if(nx < 0 || nx >= n || ny < 0 || ny >= m){ continue;}
                
                if(visited[nx][ny]) {continue;}
                
                visited[nx][ny] = true;
                pq.add(new Node(nx, ny, heightMap[nx][ny]));
            }
        }
        
        return answer;
    }
    
    static class Node implements Comparable<Node>{
        
        int x, y, h;
        Node(int x, int y, int h){
            this.x = x;
            this.y = y;
            this.h = h;
        }
        
        @Override
        public int compareTo(Node n){
            return this.h - n.h;
        }
    }
}