[백준] 자바 14719 빗물

문제

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

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

입력

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

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

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

출력

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

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

---

테스트 케이스

 

입력 1

5 5
5 2 3 1 5

출력 1

9

 

입력 2

3 3
1 2 3

출력 2

0

 

입력 3

5 6
5 0 5 0 5 0

출력 3

10

---

접근

원리

저는 그림과 같은 원리를 이용해서 문제를 풀었습니다.

벽과 벽이 만났을때만 구덩이가 생긴다!

 

1. 입력받은 값을 토대로, 맵을 만들고

2. 그 맵을 이용해서 한줄씩 검사하여 <벽 공간 벽> 구조가 나올때 마다 공간값을 더해줬습니다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static int H;
	static int W;
	static int map[][];
	static int result;
	public static void search(int line) {
		boolean flag = false;
		int cnt = 0;
		//받아 온 줄의 열 검사
		for(int i=0; i<W; i++) {
			//처음으로 벽 만났을 때
			if(map[line][i] == 1 && !flag) flag = true;
			//벽 만난 후에 공간 만났을 때
			else if(map[line][i]==0 && flag) {
				cnt++;
			}
			//공간 만나다가 벽을 다시 만났을 때
			else if(map[line][i]==1 && flag) {
				//벽을 만났는데 전에 칸이 0이였을 때
				if(map[line][i-1]==0) {
					result += cnt;
					cnt = 0;
					flag = false;
				}
				//공간 만나다가 벽을 만났고 그 다음이 바로 공간일 때
				if(i<W-1) {
					if(map[line][i+1] == 0) {
						flag = true;
					}
				}
			}
		}
	}
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    H = Integer.parseInt(st.nextToken());
	    W = Integer.parseInt(st.nextToken());
	    map = new int[H][W];
	    st = new StringTokenizer(br.readLine());
	    
	    //입력받은걸 맵으로
	    for(int i=0; i<W; i++) {
	    	int temp = Integer.parseInt(st.nextToken());
	    	for(int j=H-1; j>=0; j--) {
	    		if(temp == 0) break;
	    		map[j][i] = 1;
	    		temp--;
	    	}
	    }
//	    for (int i = 0; i < map.length; i++) {
//	    	System.out.println();
//	    	for (int j = 0; j < map[i].length; j++) {
//				System.out.print(map[i][j]+" ");
//			}
//		}
	    //한줄씩 검사
	    for(int i=0; i<H; i++) {
	    	search(i);
	    }
	    bw.write(String.valueOf(result));
	    br.close();
	    bw.flush();
	    bw.close();
	    }
	}

---

주의

<벽 공간 벽>구조도 가능하지만

<벽 공간 벽 공간 벽>구조도 가능함을 인지해야 합니다.