[백준] 2276번 : 물 채우기

2276번: 물 채우기

# 문제

N×M 크기의 물통이 있다. 이 물통의 각 칸은 높이가 다를 수도 있다. 이와 같은 물통에 물을 부었을 때, 담을 수 있는 물의 최대량을 계산하는 프로그램을 작성하시오. 물통의 테두리도 높이가 다를 수 있고, 테두리가 물통의 안쪽보다 높이가 낮을 수도 있다.

왼쪽 표는 물통의 높이를 나타낸 것이고, 오른쪽은 각 칸에 담은 물의 양을 나타낸 것이다. 이 경우가 답이 12로 최대인 경우가 된다.

# 입력

첫째 줄에 M, N(1≤N, M≤300)이 주어진다. 다음 M개의 줄에는 N개의 자연수로 각 칸의 높이가 주어진다. 각각의 높이는 1,000,000,000를 넘지 않는다.

# 출력

첫째 줄에 답을 출력한다. 답은 int 범위 이내이다. 이 값은 0이 될 수도 있다.

# 예제 입력 1

4 5

5 8 7 7

5 2 1 5

7 1 7 1

8 9 6 9

9 8 9 9

# 예제 출력 1

12

---

[우선순위 큐 + 다익스트라(?) or DFS]

솔직히 나의 계획대로 했으면 풀지 못했을 문제이다. 다음 블로그 2개를 참고하였다. 나는 언어만 Java로 바꿨을 뿐 코드는 대부분 일치한다.

codersbrunch님의 블로그

heechan3006님의 github

 

이 분들은 마치 서해의 바닷물이 차오르듯, 바닥에서부터 물이 차오르는 방법으로 구상하였다. 그렇게 되면 물통에서 가장 높은 곳까지 물이 차올랐다가 물이 다시 빠질 때 특정 칸 (y, x)에 물이 들어있으려면 (y, x)기준 상 하 좌 우칸 모두 이 곳보다 높이가 높아야 한다.

 

 그리고 잠기는 구역이 생길 때 (수면의 높이) - (잠기는 구역의 높이) 합을 구하면 답을 구할 수 있다고 하셨다. 또한 낮은 수면부터 채워나가기 위해 우선순위 큐를 사용하고 특정 칸에서 DFS를 이용해 현재의 수면보다 높은 칸이 나오면 우선순위 큐에 넣고, 그렇지 않으면 현재 수면까지 물을 채우는 방식으로 풀이를 하셨다.

 

 현재 그래프에 관한 공부를 하고 있지만, 이 문제를 보며 보다 다양한 방법으로 접근하고 많은 문제를 풀며 경험치를 누적해야겠다는 생각이 들었다...

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int y, x, w;
        public Edge(int y, int x, int w){
            this.y=y;
            this.x=x;
            this.w=w;
        }
        @Override
        public int compareTo(Edge o) {
            return w-o.w;
        }
    }
    static boolean[][] visit;
    static int[][] table;
    
    static int m, n;
    
    static Queue<Edge> Q = new PriorityQueue<>();
    
    static int[] Y = {-1, 1, 0, 0};
    static int[] X = {0, 0, -1, 1};

    static int water = 0;
    
    static void Dijkstra(){

        while(!Q.isEmpty()){
        
            Edge edge = Q.poll();
            
            int y = edge.y;
            int x = edge.x;
            int w = edge.w; //현재 위치한 곳의 높이

            for(int a=0; a<4; a++) {
                int ny = y + Y[a];
                int nx = x + X[a];

                if ((ny >= 0 && ny < n) && (nx >= 0 && nx < m) && !visit[ny][nx]){
                    visit[ny][nx] = true;

                    //내 주변에 나보다 높은 곳이 있다면, 그 곳을 울타리라고 생각한다.
                    if(table[ny][nx] > w)
                        Q.add(new Edge(ny, nx, table[ny][nx]));

                    //w >= table[ny][nx]
                    //내 주변에 나와 같거나 낮은 곳이 있다면, 그 곳으로 물을 채워주고(현재 높이 - 그 곳의 높이), 채워준 만큼 water에 합한다.
                    //그리고 그곳에서 더 물을 채울 곳이 있나 탐색
                    else if(table[ny][nx] <= w){
                        water += w - table[ny][nx];
                        Q.add(new Edge(ny, nx, w));
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        table = new int[n][m];
        visit = new boolean[n][m];

         for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                table[i][j] = Integer.parseInt(st.nextToken());

                if(i == 0 || j == 0 || i == n-1 || j == m-1){
                    visit[i][j] = true;
                    Q.add(new Edge(i, j, table[i][j]));
                }
            }
        }

         Dijkstra();
         System.out.println(water);
    }
}