[백준]#14719 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1

4 4
3 0 1 4

예제 출력 1

5

예제 입력 2

4 8
3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5
0 0 0 2 0

예제 출력 3

0

풀이

이 문제는 DFS 알고리즘을 이용해서 쉽게 풀 수 있는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static boolean[][] visited;
    static int N;
    static int M;
    static int[][] map;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        map = new int[N][M];
        visited = new boolean[N][M];
        String[] input = br.readLine().split(" ");

        for(int i=0; i<M; i++) {
            int k = Integer.parseInt(input[i]);

            for(int j=0; j<k; j++)
                map[j][i] = 1;
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(!visited[i][j] && map[i][j]==1) {
                    visited[i][j] = true;
                    dfs(i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    static void dfs(int x, int y) {
        int ny = y;
        while(true) {
            ny++;

            if(ny>=M)
                break;

            if(map[x][ny]==1) {
                cnt += (ny-y-1);
                break;
            }

            visited[x][ny] = true;
        }
    }
}