백준 빗물 14719

2020-10-26

구현, 백준, 알고리즘, 완전탐색

1. 백준 빗물 14719 문제

1.1. 문제

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

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

1.2. 입력

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

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

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

1.3. 출력

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

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

1.4. 예제 입력 1

4 4
3 0 1 4

1.5. 예제 출력 1

1.6. 예제 입력 2

4 8
3 1 2 3 4 1 1 2

1.7. 예제 출력 2

1.8. 예제 입력 3

3 5
0 0 0 2 0

1.9. 예제 출력 3

1.1. 컴퓨팅적 사고

2차원 세계 블록에서 빗물이 얼만큼 고이는지를 확인하는 문제이다. 이 문제는 이전에 풀어보았던 창고다각형 문제와 비슷하다.
백준 창고다각형 2304 문제
창고다각형 2304 문제 풀이
이 문제에서 가장 중요한 점은 2차원 세계블록에서 블록내부의 빈 공간이 생길 수 없도록 빗물이 얼마나 고이는지를 확인하면 된다. 빗물이 고이지 않았으면 0, 고였으면 1로 처리해준다. 즉, 블록의 면적을 구할 수 있다.

블록의 최대 높이의 인덱스 구하기

블록의 높이가 가장 높은 인덱스의 값을 구해주어야 합니다. 그 이유는 지붕의 높이가 가장 높은 인덱스의 값을 기준으로 빗물을 고이게 만들어야하기 때문입니다.

블록의 높이가 있는 가장 작은 인덱스와 큰 인덱스 구하기

블록의 높이가 있는 가장 작은 인덱스와 큰 인덱스를 구해주어야 하는이유는 블록의 최대 높이의 인덱스를 기준으로 좌측, 우측의 최대로 가질 수 있는 블록의면적을 구해야하기 때문입니다.

문제 풀이

map이라는 배열을 하나 선언합니다. 배열의 인덱스값에는 블록의 인덱스값이 들어가게 되고 값에는 블록의 높이가 들어가게 됩니다.
값을 입력 받는것과 동시에 블록의 높이를 가진 인덱스의 최댓값과 최솟값을 Math.max(), Math.min() 함수를 사용하여 구해주게 됩니다.
그리고, 지붕의 최댓값을 가지는 인덱스의값을 구해줍니다. 현재 입력받은 인덱스의 값(블록의 높이)가 현재 블록의 높이 보다 클 경우 해당 인덱스 값을 갱신시켜주게 됩니다.
좌측의 경우, 우측의 경우를 나누어서 블록의 만드는 값을 더해주면서 진행해줍니다.

좌측

좌측의 경우 블록의 높이를 가지는 인덱스의 최솟값~블록의 높이가 가장 큰 블록의 인덱스값 까지 값을 순회하면서 h의 값을 갱신하면서 순회하는 값의 높이가 더 클 경우에 sum의 값을 더해주게 됩니다.
예를 들면, 높이가 (2,1), (2,3)의 경우를 비교해보겠습니다.
높이가 idx=0 h= 2, idx=1 h= 1일 경우 현재 idx=0의 높이가 idx=1보다 더 크므로, Math.max() 함수를 사용하여 더 큰 h값으로 sum의 값을 더해주면서 진행합니다.

// left -> max_hight_idx
int sum = 0;
int h = 0;
for(int i=min_idx; i<max_hight_idx; i++){
    h = Math.max(h, map[i]);
    sum += h;
}

우측

우측의 경우는 블록의 높이를 가지는 인덱스의 최댓값~블록의 높이가 가장 큰 블록의 인덱스값까지 값을 순회하면서 h의 값 역시 최댓값으로 sum에 값을 더해줍니다. 그 이유는 위와 같습니다.

최종적으로 sum의 값에는 좌측에서의 최대로 가질 수 있는 높이값, 우측에서 최대로 가질 수 있는 높이값을 가지고 있습니다. 하지만, 아직 구해지지않은 값은 max_hight_idx의 값 즉, 가장 높은 블록의 값을 더해지지않은 상태이기 때문에 map[max_hight_idx]의 값으로 최종 결과값을 출력시켜주게 됩니다.

h = 0;
// right -> max_hight_idx
for(int i=max_idx; i>max_hight_idx; i--){
   h = Math.max(h, map[i]);
   sum += h;
}

블록의 빗물만 구하는 방법
기존의 지붕의 높이에 기둥을 넣은 부분의 면적을 구하려면 기존의 블록의 채워진 모든 블록+빗물의 면적에서 - 블록의 값을 빼주면 현재 채워진 빗물의 양(면적)을 확인할 수 있습니다.
백준 창고다각형 2304 문제와 유사한 문제입니다.

결과적으로 모든 영역의 넓이에서 - 각 영역의 기존의 값을 빼준다면 빗물이 채워진 부분의 넓이를 구할 수 있습니다.

int left_sum = 0;
int right_sum = 0;

// left_sum
int sum = 0;
int h = 0;
for(int i=min_idx; i<max_hight_idx; i++){
    left_sum += map[i];
    h = Math.max(map[i], h);
    sum += h;
}

// right_sum
h = 0;
for(int i=max_idx; i>max_hight_idx; i--){
    right_sum += map[i];
    h = Math.max(map[i], h);
    sum += h;
}

이런형식으로 값을 구할 수 있겠습니다.

1.2. 소스코드

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

public class 빗물14719 {
    static int map[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        map = new int[m];
        st = new StringTokenizer(br.readLine(), " ");

        int max_idx = 0;
        int min_idx = 0;
        int max_hight_idx = 0;
        for(int i=0; i<m; i++){
            int x = i;
            int y = Integer.parseInt(st.nextToken());
            map[x] = y;
            max_idx = Math.max(max_idx, x);
            min_idx = Math.min(min_idx, x);

            if(map[x] > map[max_hight_idx]){
                max_hight_idx = x;
            }
        }

        int left_sum = 0;
        int right_sum = 0;

        // left_sum
        int sum = 0;
        int h = 0;
        for(int i=min_idx; i<max_hight_idx; i++){
            left_sum += map[i];
            h = Math.max(map[i], h);
            sum += h;
        }

        // right_sum
        h = 0;
        for(int i=max_idx; i>max_hight_idx; i--){
            right_sum += map[i];
            h = Math.max(map[i], h);
            sum += h;
        }
        int answer = sum - (left_sum + right_sum);
        System.out.println(answer);
    }
}

AlgorithmBOJ