[백준] 14719. 빗물 (자바)

14719번: 빗물

 

문제

2차원으로 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고이고, 비는 충분히 많이 온다고 한다.

고이는 빗물의 총량은 얼마일까?

 

입출력

4 4 // 세로, 가로 길이
3 0 1 4 // 블록이 쌓인 높이

-> 블록 내부의 빈 공간이 생길 수 없다.

-> 2차원 세계의 바닥은 항상 막혀있다.

 

---

접근 과정

• 주어진 예시 그림을 보면서 생각했을 때, 왼쪽 끝지점부터 오른쪽으로 가면서 빗물이 쌓이는 경우에 대해 확인했습니다.
• 기존에 시작되는 지점의 블록과 같은 높이이거나 더 큰 높이를 만나면 빗물이 고이게 됩니다.
• 빗물이 고이면 두 벽(start, end)으로 둘러싸인 웅덩이의 깊이(고인 빗물)를 구해줍니다.
• 이 과정은 왼쪽에서 오른쪽으로 향하면서 빗물이 고이는 것을 조사한 것이므로,
  반대로 오른쪽에서 왼쪽으로 오면서 빗물이 고이는 부분에 대해서도 조사를 한 번 더 해줘야 합니다.

 

풀이 과정

예시의 문제처럼 3 1 2 3 4 1 1 2 가 들어온다면, 

 

1. 왼쪽부터 오른쪽으로 가면서 start = 0 의 블록보다 높이가 같거나 커지는 지점 i를 찾습니다.

i를 찾으면 start+1~ i-1 까지는 최대 빗물이 start까지 쌓입니다 -> blocks[start] ≤ blocks [i]인 지점을 찾은 것이기 때문.

모아지는 빗물을 최종 answer에 더해줍니다.

이제 다시 빗물이 모아지는 시점이 시작될 것이므로 start를 i로 갱신해줍니다.

 

 

2. 이어서 start지점보다 높거나 같은 만큼 쌓인 지점 i를 찾아주고, 나머지 1번과 같은 작업을 수행합니다.

여기서는 start와 i 사이에 블록이 없기 때문에 빗물이 쌓이지 않고, start지점을 다시 i로 바꿔줍니다.

3. 이어서 바뀐 start를 기준으로 같거나 더 높게 쌓인 블록을 찾지만, 더 이상 존재하지 않습니다.

따라서 현재까지 구한 빗물 부분은 파란색으로 칠한 부분입니다.

 

4. 이제 반대로 오른쪽에서 왼쪽으로 오면서 고이는 빗물을 계산해 준다면, 고이는 모든 빗물을 계산할 수 있습니다.

* 여기서 주의!

왼쪽에서 오른쪽으로 갈 때 start블록높이와 i블록높이가 같을 때의 빗물을 answer에 더해줬다면,

오른쪽에서 왼쪽으로 갈 때에는 같은 높이일 때의 웅덩이는 지나칩니다.

---

전체 코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		int w = Integer.parseInt(s[1]);
		int[] blocks = new int[w]; //블록 높이 담기. 
		
		s = br.readLine().split(" ");
		for(int i=0;i<w;i++) blocks[i]=Integer.parseInt(s[i]);
		
		int start=0; // 빗물이 고이는 왼쪽 
		int answer=0; // 총 빗물 
		
		//왼쪽에서 오른쪽으로 가면서
		//start 높이보다 커지거나 같을 때 고인 빗물 계산
		// 1 0 1 0 3 3 0 5 
		for(int i=0;i<w;i++) { 
			if(blocks[i]>=blocks[start]) { //i번째 블록이 start 블록보다 크거나 같아지면 -> 빗물이 고임.
				int rainMax = Math.min(blocks[start], blocks[i]);
				for(int j=start+1;j<i;j++) {
					answer+=rainMax-blocks[j]; //빗물 더해주기.
				}
				
				start=i; //빗물 담을 시작위치를 i로 바꿔주기.
			}
		}
		//오른쪽에서 왼쪽으로 가면서
		//start 높이보다 커질 때만 빗물 계산
		// 6 0 5 4 0 3 0 1
		start=w-1;
		for(int i=w-1;i>=0;i--) {
			// i번째 블록이 start블록보다 클 때 빗물 고임.
			// 블록이 같아서 고이는 경우는 위에서 했으므로, blocks[i]>blocks[start]만 생각.
			if(blocks[i]>blocks[start]) { 
				int rainMax=Math.min(blocks[start], blocks[i]); //빗물이 최대로 쌓일 수 있는 높이.
				
				for(int j=start-1;j>i;j--) { // start ~ i 사이에 고이는 
					answer+=rainMax-blocks[j]; // 빗물 더해주기 
				}
				
				start=i; // start보다 큰 블록이 나온 것이기 때문에 start 바꿔줌.
			}
		}
		
		System.out.println(answer);
	}
}