BOJ_14719 빗물 C++

HDuckkk·2023년 7월 22일

boj

Beakjoon Online Judge

목록 보기

10/13

BOJ 14719 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

문제 풀이

~~오랜만에~~ 백준 포스팅이다.

바로 본론으로 들어가자.

처음에는 단순히 시뮬레이션을 생각했다. 조건으로 주어진 맵의 크기도 그리 크지 않았으며 중복으로 연산이 시행되어 시간초과를 일으킬 가능성이 있는 구간도 크게 떠오르지 않았다.

중간쯤에 BFS로 해결하면 보다 직관적이고 편할 것이란 생각이 들었다.

위와같은 상황을 생각해보자.

여기서 검은색 공백은 벽을 의미하며 파란색 공간은 빗물을 의미한다.

위와같은 상황에서 문제의 조건대로 시행된다면 어떻게 될까?

바로 다음과 같다는 것을 알 수 있다.

~~당연한거 아닌가?~~
이 문제에서 원하는 것은 빗물이 빠져나간 뒤 얼마만큼의 빗물이 남았는 가 이다.

이를 구현하기 위해서 나는 BFS를 채택했다. BFS를 이용하여 어떤식으로 구현을 하였냐면 빗물이 빠져나가는 반대의 방향으로 빗물을 탐색해나가도록 했다.

여기서 몇가지 특징을 확인할 수 있다!

아래방향으로의 탐색을 이루어지지 않는다.
탐색의 시작구간은 벽이아닌 가장 왼쪽, 오른쪽 열이다.

왜 이러한 특징을 가져야하면, 우선 아래방향으로의 탐색을 허용해버리면 고이는 빗물을 특정할 수 없을 것이다.

또한 외벽부분부터 탐색을 시작하되 벽이 아니라 빈 공간이여야만 빗물이 빠져나올 수 있기 때문에 외벽부터 탐색을 시작하되 벽이 아니어야한다.

위의 특징을 유의하며 코드를 작성하면 다음과 같다.

정답 코드

// BOJ 14719
#include <iostream>
#include <queue>
#define MAX 501
using namespace std;
using pii = pair<int, int>;

int H, W;
int dx[4] = {0,-1,1}; /* y축으로 내려가는 방향을 없앰 */
int dy[4] = {1,0,0};
int map[MAX][MAX];

void init(){
    cin >> H >> W;

    for(int i=1; i<=W; i++){

        int temp;
        cin >> temp;

        for(int j=temp; j>=1; j--){
            map[j][i] = 1;
        }
    }

    /* print */
    // cout << "--\n";
    // for(int i=H; i>=1; i--){
    //     for(int j=1; j<=W; j++){
    //         cout << map[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
}

void solution(){

    for(int i=0; i<2; i++){

        if(i == 0){ /* 왼편 */

            for(int j=1; j<=H; j++){

                if(map[j][1] == 1) continue;

                queue<pii> q;
                q.push({j,1});
                map[j][1] = 2;

                while (!q.empty()){
                    int cury = q.front().first;
                    int curx = q.front().second;
                    q.pop();

                    for(int k=0; k<3; k++){
                        int nexy = cury + dy[k];
                        int nexx = curx + dx[k];

                        if(nexx <= 0 || nexy <= 0 || nexx > W || nexy > H) continue;
                        if(map[nexy][nexx] == 1) continue;
                        if(map[nexy][nexx] == 2) continue;

                        q.push({nexy, nexx});
                        map[nexy][nexx] = 2;
                    }
                }
            }

        }else{ /* 오른편 */

            for(int j=1; j<=H; j++){

                if(map[j][W] == 1) continue;

                queue<pii> q;
                q.push({j,W});
                map[j][W] = 2;

                while (!q.empty()){
                    int cury = q.front().first;
                    int curx = q.front().second;
                    q.pop();

                    for(int k=0; k<3; k++){
                        int nexy = cury + dy[k];
                        int nexx = curx + dx[k];

                        if(nexx <= 0 || nexy <= 0 || nexx > W || nexy > H) continue;
                        if(map[nexy][nexx] == 1) continue;
                        if(map[nexy][nexx] == 2) continue;

                        q.push({nexy, nexx});
                        map[nexy][nexx] = 2;
                    }
                }
            }

        }

    }

    // cout << "--\n";
    // for(int i=H; i>=1; i--){
    //     for(int j=1; j<=W; j++){
    //         cout << map[i][j] << " ";
    //     }
    //     cout << "\n";
    // }


    int ANS = 0;
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            if(map[i][j] == 0){
                ANS++;
            }
        }
    }

    cout << ANS << "\n";
}

int main(){

    init();
    solution();


    return 0;
}