[Problem Solving] BOJ 14719 : 빗물

문제 링크 : https://www.acmicpc.net/problem/14719

 

2차원 세계의 단면이 있을 때, 고이는 빗물의 총량을 구하는 문제이다.

loop로 밑의 행부터 위의 행으로 빗물을 채운다. 행에서 맨 왼쪽이나 맨 오른쪽에 블럭이 없어서 빗물이 고일 수 없다면 인접한 빗물을 모두 없앤다. loop가 끝나면 빗물을 모두 count해서 answer를 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <cmath>
#include <climits>
#define endl '\n'
using namespace std;

int answer = 0;
int H, W;
int blocks[501][501];

void input()
{
    cin >> H >> W;
    fill(&blocks[0][0], &blocks[H - 1][W], 1);
    for (int i = 0; i < W; i++)
    {
        int h;
        cin >> h;
        for (int j = 0; j < H - h; j++)
        {
            blocks[j][i] = 0;
        }
    }
}

void solution()
{
    for (int i = H - 1; i >= 0; i--)
    {
        for (int j = 0; j < W; j++)
        {
            if (blocks[i][j] == 0)
                blocks[i][j] = 2;
        }
        int j = 0;
        if (blocks[i][j] == 2)
        {
            blocks[i][j] = 0;
            while (j + 1 < W && blocks[i][j + 1] == 2)
            {
                blocks[i][j + 1] = 0;
                j++;
            }
        }
        j = W - 1;
        if (blocks[i][j] == 2)
        {
            blocks[i][j] = 0;
            while (j - 1 >= 0 && blocks[i][j - 1] == 2)
            {
                blocks[i][j - 1] = 0;
                j--;
            }
        }
    }

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (blocks[i][j] == 2)
                ++answer;
        }
    }
}

void output()
{
    cout << answer << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}