[BOJ/JAVA] 백준 14719 : 빗물 (자바)

문제 정보

  문제명   - 빗물
  난이도   - 골드 V
문제 번호 - 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을 출력하여라.

---

예제 입력/출력

예제 입력	예제 출력
4 4 3 0 1 4	5
4 8 3 1 2 3 4 1 1 2	5
3 5 0 0 0 2 0	0

---

힌트

---

알고리즘 분류

● 구현
● 시뮬레이션

---

소스코드

package Lv3_Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 구현, 시뮬레이션
 * https://www.acmicpc.net/problem/14719
 */
class RainWater{
    int index;
    int height;

    public RainWater(int index, int height){
        this.index = index;
        this.height = height;
    }
}

public class BOJ_G5_14719_빗물 {
    public static int[] map;
    public static RainWater preLeft;
    public static RainWater preRight;
    
    public static int getStagnantWater(RainWater pre, RainWater current){
        int stagnantWater = 0;
        // 양 끝 최소 높이 판단
        int height = Math.min(pre.height, current.height);
        for (int n = pre.index+1; n < current.index; n++) {
            // 평지에 언덕만 솟아 있을 경우 예외 처리
            stagnantWater += height - map[n];
        }

        return stagnantWater;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder str = new StringBuilder();
        int result = 0;

        // 세로길이 H
        int H = Integer.parseInt(st.nextToken());
        // 가로길이 W
        int W = Integer.parseInt(st.nextToken());

        // W개의 숫자 출력
        map = new int[W];
        
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            map[i] = Integer.parseInt(st.nextToken());
            // Integer.parseInt(st.nextToken());
        }
        // 시작점
        preLeft = new RainWater(0,map[0]);
        preRight = new RainWater(W-1,map[W-1]);

        for (int i = 1; i < W; i++) {
            // 두개가 만나게 되면 끝
            if(preLeft.index >= preRight.index)
                break;
            // pre보다 같거나 높고, 바로 다음 높이가 떨어 진다면
            // 웅덩이로 판단하고 빗물양 계산. 
            if(preLeft.height <= map[i]){
                result += getStagnantWater(preLeft, new RainWater(i, map[i]));
                // 시작점 최신화
                preLeft = new RainWater(i, map[i]);
            }

            if(preRight.height <= map[(W-1)-i]){
                result += getStagnantWater(new RainWater((W-1)-i, map[(W-1)-i]), preRight);
                // 시작점 최신화
                preRight = new RainWater((W-1)-i, map[(W-1)-i]);
            }
            // pre보다 낮으면 그냥 지난다.
        }

        str.append(result);
        System.out.println(str.toString());
        br.close();
    }
}

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---