[JAVA] BOJ(백준) - 빗물 -14719

문제내용

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

14719번: 빗물

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

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

입력

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

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

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

출력

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

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

---

문제 접근 방법

배열을 이용해서 그림대로 풀면되는 문제이다.

간단하게 로직을 설명하자면 아래와 같다.

 

로직 설명

1. 배열 만들기
   2차원 배열을 선언해서 그림과 같은 배열을 만들어주는 작업이다.
   그림에서 블록이 있는 검은색 부분은 표시된 부분은 1로 표시하고 흰색으로 표시된 부분은 0으로 표시해준다.
   참고로 2차원 배열의 선언은 행의 경우 높이(H), 열의 경우 가로길이(W)로 하여 선언해 줬다.
   
   
2. 빗물 총량 계산하기
   2차원 배열을 이용해 그림처럼 배열을 만들었다면 빗물 총량을 계산해주면된다.
   이때 문제에서 가장 밑바닥은 항상 막혀있다고 가정해줬기 때문에 좌우에 블록이 있는지 없는지만 살펴주면 된다.
   따라서 각 행마다 블록과 블록 사이에 있는 빗물을 카운트하여 더해주면 된다는 말이다.
   
   예를들어 문제에서 주어진 그림같은 블록의 경우
   첫번째 행에서는 좌우로 막힌 블록이 없기 때문에 빗물의 총량 = 0이 된다.
   두번째 행에서는 좌우로 막힌 블록이 0번열과 3번열이 존재한다. 따라서 빗물의 총량 = 3 - 0 - 1이 된다.
   세번째 행에서는 좌우로 막힌 블록이 0번열과 2번열 , 4번열과 7번열이 존재한다.
   따라서 빗물의 총량 = (2-0-1) + (7-4-1)이 된다.
   네번째 행에서는 모두 블록으로 채워져 있기 때문에 빗물의 총량 = 0이 된다.
   
   즉, 첫번째 ~ 네번째 행까지 빗물의 총량을 모두 더하면 0 + 2 + 3 + 0 = 5 가 되고 5를 출력해주면 답이된다.

코드를 보자.

 

 

---

풀이

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

public class Main {
	static int[][] arr; //블록배열
	static int answer = 0; //빗물총량
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int h = Integer.parseInt(st.nextToken());//블록 최고 높이
		int w = Integer.parseInt(st.nextToken());//블록 최고 넓이
		arr = new int[h][w];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<w; i++) {
			//해당하는 열(i)에 블록을 얼마나 쌓을지 알려주는 변수
			int tempH = Integer.parseInt(st.nextToken());
			createArr(tempH,i); //createArr로 블록 배열 만들기
		}
		
		//행을 하나씩 살피면서 가로로 1과 1사이에 있는 빗물 카운트
		for(int i=0; i<h; i++) 
			answer += rain(i,w);
		System.out.println(answer);
	}
	
	//w번째 열에서 h만큼 arr배열에 밑에서 부터 1로 표기해주기.
	public static void createArr(int h, int w) {
		for(int i=arr.length-1; i>=arr.length-h; i--) 
			arr[i][w] = 1;
	}
	
	//가로 한줄에 빗물이 얼마나 있는지 카운트
	public static int rain(int h, int w) {
		int start = -1;//시작 블록
		int end = -1;//끝 블록
		int cnt = 0;
		
		//h(높이)번째 가로줄에 해당하는 0번열 ~ 마지막열까지 빗물 총량 구하기.
		for(int i=0; i<w; i++) {
			int checkWall = arr[h][i];
			
			//start 블록이 초기화 안됐으면 초기화
			if(checkWall==1 && start==-1) {
				start = i;
				continue;
			}
			
			//end 블록이 초기화 안됐으면 초기화
			if(checkWall==1 && start!=-1 && end==-1) {
				end = i;
				cnt += end-start-1;//첫번째 빗물 총량 카운트
				continue;
			}
			
			//start와 end블록 모두 값이 있는상태에서
			//또 다시 블록이 나온다면 start와 end를 갱신시켜줌.
			if(checkWall==1) {
				start = end;
				end = i;
				cnt += end-start-1;//첫번째 이후 빗물 총량 계속 카운트
			}
		}
		return cnt;
	}
}

---

마치며

그림대로 문제를 풀어내면되고 그림처럼 로직을 짜는게 어려운 문제는 아니였다.