백준 14719번 빗물

🔒[문제 url]

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

🔑알고리즘

입력받은 블록의 높이를 통해 2차원 배열을 생성하자. 블록이 있는 지점은 1로 표기하여 구별한다.

• 빗물이 고이기 위한 조건은?
  • 현재 지점의 왼쪽과 오른쪽이 모두 벽으로 막혀있어야한다.
    따라서, 2차원 배열의 블록이 없는 모든 지점에 대해 왼쪽과 오른쪽을 검사하여 빗물의 고임 여부를 판별한다.

🐾부분 코드

void INPUT()
{
    IAMFAST
    cin >> h >> w;
    for (int i = 1; i <= w; i++)
    {
        int n; cin >> n;
        for (int j = 0; j < n; j++)
            block[h - j][i] = 1;
    }
}

<입력 함수>
입력받은 블록의 높이를 통해 2차원 배열을 초기화한다.
블록의 높이가 $n$이라면, $h$부터 $h-n-1$의 높이에 블록이 존재하게 된다.

bool isBlocked(int r, int c)
{
    bool left = false, right = false;
    // 양 끝자리면 빗물이 고일 수 없음
    if (c == 1 || c == w) return false;

    // 왼쪽
    for (int i = c - 1; i >= 1; i--)
        if (block[r][i] == 1)
        {
            left = true;
            break;
        }

    // 오른쪽
    for (int i = c + 1; i <= w; i++)
        if (block[r][i] == 1)
        {
            right = true;
            break;
        }

    return (left && right);
}

<왼쪽과 오른쪽 검사>
블록이 없는 지점에 빗물이 고일 수 있는지 여부를 판별한다.
이때, 가장 왼쪽과 가장 오른쪽에는 빗물이 고일 수 없음에 유의한다.
현재 지점을 기준으로 왼쪽과 오른쪽에 모두 블록이 있다면, true를 반환한다.

void SOLVE()
{
    for(int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (block[i][j] == 0 && isBlocked(i, j))
                ans++;
    cout << ans;
}

<빗물의 총량>
블록이 없는 모든 지점에 대해 검사함으로써 빗물의 총량을 측정한다.

🪄전체 코드

#include<iostream>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int h, w;
int block[501][501];

int ans = 0;

void INPUT()
{
    IAMFAST
    cin >> h >> w;
    for (int i = 1; i <= w; i++)
    {
        int n; cin >> n;
        for (int j = 0; j < n; j++)
            block[h - j][i] = 1;
    }
}

bool isBlocked(int r, int c)
{
    bool left = false, right = false;
    // 양 끝자리면 빗물이 고일 수 없음
    if (c == 1 || c == w) return false;

    // 왼쪽
    for (int i = c - 1; i >= 1; i--)
        if (block[r][i] == 1)
        {
            left = true;
            break;
        }

    // 오른쪽
    for (int i = c + 1; i <= w; i++)
        if (block[r][i] == 1)
        {
            right = true;
            break;
        }

    return (left && right);
}

void SOLVE()
{
    for(int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            if (block[i][j] == 0 && isBlocked(i, j))
                ans++;
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

1년 전에 풀었던 문제다. 아니 그런데 왜 지금보다 깔끔하게 잘 짜는 것같지...?