[백준] 14719번 빗물 c++

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

14719번: 빗물

문제

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

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

입력

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

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

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

출력

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

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

 

문제접근 및 풀이

- 빗물이 고이는 위치를 어떻게 찾느냐가 관건이었다.

- 해당 칸을 기준으로 양 옆 사이드에 벽이 존재하면 빗물이 고인다는 것으로 판단했다.

- 전체 배열을 탐색하면서 각 줄에 대해서 몇칸의 빗물을 받을 수 있는지 확인했다.

- 변수 2개를 두었다.

find : 벽을 발견했는지 못했는지 확인한다.

count : 빗물이 고일 수 있는 칸 개수를 센다.

 

다음과 같은 방식으로 탐색을 진행하였다.

- 각 줄 탐색시 벽을 만나면 find가 true가 된다.

- find가 true인 상태에서 빈칸을 만나면 count가 1씩 증가한다.

- 다시 벽을 만나면 결과값에 지금까지 찾은 count를 더하고 count를 0으로 초기화시킨다.

 

#include <iostream>
#define VMAX 500

using namespace std;

int main()
{
    int result=0;
    int input[VMAX];
    int b[VMAX][VMAX]={0};
    int h,w; cin >> h >> w;
    for(int i=0; i<w; i++) cin >> input[i];
    
    for(int i=0; i<w; i++){
        for(int j=0; j<input[i]; j++){
            b[j][i]=1;
        }
    }
    
    for(int i=0; i<h; i++){
        int find = false;
        int count=0;
        for(int j=0; j<w; j++){
            if(find==true && b[i][j]==0) count++;
            if(find==true && b[i][j]==1){
                result+=count;
                count=0;
            }
            if(find==false && b[i][j]==1) find=true;;
        }
    }
    
    cout << result;
    
    return 0;
}

 

느낀점

다른 분들의 풀이를 몇개 찾아봤다. 다른 풀이들 보다 굉장히 간단한 방식으로 푼것 같아 뿌듯했다.