문제

https://www.acmicpc.net/problem/14719

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

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

---

입력

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

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

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

---

출력

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

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

---

풀이

접근방법

시간제한 1초, 메모리512MB, (1 ≤ H,W ≤ 500)이다.

가장 단순하게 생각한다.
입력을 2차원 배열에 표시해 본다.
블록이 없는 곳은 비가 고일 수 있는 곳이다.
모든 블록이 없는 점을 기준으로

• 블록이 없는 점에서 왼쪽으로 기둥이 있다면, 왼쪽으로는 흐를 수 없다.
• 블록이 없는 점에서 오른쪽으로 기둥이 있다면, 오른쪽으로는 흐를 수 없다.
  즉 양쪽으로 기둥이 있다면 물이 고이는 지점이다.

생각해 보면 좋을 점.

빨간색 지점이 물이 고이는 지점이라면, 노란색 지점도 당연히 물이 고인다.
빨간색 지점에 물이 고이지 않는다면, 노란색 지점 역시 물이 고이지 않는다.

---

코드

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

public class Main {

	static int W, H;
	static int[][] map;

	final static int WALL = 1; // 블록
	final static int BLANK = 0; // 빈 공간
	final static int POSSIBLE = 8; // 고이는 경우
	final static int IMPOSSIBLE = 9; // 고이지 않는 경우

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] splitedLine = in.readLine().split(" ");
		H = stoi(splitedLine[0]);
		W = stoi(splitedLine[1]);
		map = new int[H][W + 2];

		splitedLine = in.readLine().split(" ");

		// 좌우로 한 칸씩 추가로 주고, 기둥을 세운다.
		for (int i = 0; i < W; ++i) {
			int k = stoi(splitedLine[i]);
			for (int j = 0; j < k; ++j) {
				map[H - j - 1][i + 1] = 1;
			}
		}

		int result = 0;
		for (int i = 0; i < H; ++i) {
			for (int j = 1; j <= W; ++j) {
				if (map[i][j] == BLANK)
					simulation(i, j);
				if(map[i][j] == IMPOSSIBLE)
					result++;
			}
		}
		System.out.println(result);

		printState();
	}

	// 고이는 물인지 확인한다.
	private static void simulation(final int i, final int j) {
		boolean isOkayToLeft = leftCheck(i, j);
		boolean isOkayToRight = rightCheck(i, j);
		if (isOkayToLeft && isOkayToRight)
			map[i][j] = POSSIBLE;
		else
			map[i][j] = IMPOSSIBLE;
	}

	private static boolean leftCheck(final int i, final int j) {
		int leftIndex = j;
		while (leftIndex >= 0) {
			if (map[i][leftIndex] == IMPOSSIBLE) return false;
			if (map[i][leftIndex] == POSSIBLE) return true;
			if (map[i][leftIndex] == WALL) return true;
			if (map[i][leftIndex] == BLANK)
				leftIndex--;
		}
		return false;
	}

	private static boolean rightCheck(final int i, final int j) {
		int rightIndex = j;
		while (rightIndex <= W) {
			if (map[i][rightIndex] == IMPOSSIBLE) return false;
			if (map[i][rightIndex] == POSSIBLE) return true;
			if (map[i][rightIndex] == WALL) return true;
			if (map[i][rightIndex] == BLANK)
				rightIndex++;
		}
		return false;
	}

	private static void printState() {
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W + 2; ++j)
				System.out.print(map[i][j]);
			System.out.println();
		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}