[백준][C++] 30508: 고인물이싫어

문제

풀이

그래프 탐색, 누적합 문제이다.

 

횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 

• 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 이상인 칸은 물이 빠진다.

 

신발을 딛을 수 있는 방법의 수는 2차원 배열의 누적합으로 구한다. 

위의 그림에서 초록색 영역의 합을 구해보자.

• 파란색 영역을 모두 한번씩 더한다면 빨간색 영역은 두 번 더해진다. 
• 그러므로, 파란색 영역을 한번 더하고, 빨간색 영역을 한번 빼면 초록색 영역의 합을 구할 수 있다. 

for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num[i][j];
        }
    }

 

(x1, y1)부터 (x2, y2) 영역의 합을 구해보자. 위의 그림에서 초록색 부분이다. 

• 파란색 영역에서 빨간색 영역을 한번씩 뺀다. 노란색 영역은 두 번 빼진다.
• 그러므로, 파란색 영역에서 빨간색 영역을 한번 빼주고, 노란색 영역을 한번 더하면 초록색 영역을 구할 수 있다.

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1- 1][y1 - 1]

 

코드

#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;

typedef struct
{
    int x;
    int y;
}block;

queue<block> bfs;
int move_x[4] = { 0, 0, 1, -1 };
int move_y[4] = { 1, -1, 0, 0 };

int road[1001][1001];
bool water[1001][1001];
int water_sum[1001][1001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    int h, w;
    cin >> N >> M;
    cin >> h >> w;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            cin >> road[i][j];
        }
    }
    memset(water, true, sizeof(water));

    int K;
    cin >> K;
    for (int i = 0; i < K; ++i)
    {
        int x, y;
        cin >> x >> y;

        // 하수구에서부터 BFS 시작
        water[x][y] = false;
        bfs.push({ x, y });
    }

    // BFS로 어느 칸의 물이 빠지는지 탐색한다.
    while (!bfs.empty())
    {
        block current = bfs.front();
        bfs.pop();

        for (int i = 0; i < 4; ++i)
        {
            int next_x = current.x + move_x[i];
            int next_y = current.y + move_y[i];

            if (next_x < 1 || next_x > N || next_y < 1 || next_y > M || !water[next_x][next_y])
            {
                continue;
            }

            // 현재 칸보다 길의 높이 이상인 칸은 물이 빠진다.
            if (road[current.x][current.y] <= road[next_x][next_y])
            {
                water[next_x][next_y] = false;
                bfs.push({ next_x, next_y });
            }
        }
    }

    // (1, 1)에서 (i, j)칸 까지 물이 있는 칸의 수
    // 누적합
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            water_sum[i][j] = water_sum[i - 1][j] + water_sum[i][j - 1] - water_sum[i - 1][j - 1] + water[i][j];
        }
    }

    int answer = 0;
    // (i, j)칸에서 (i - h + 1, j + w - 1)칸까지 물이 없다면 answer++
    for (int i = 1; i <= N - h + 1; ++i)
    {
        for (int j = 1; j <= M - w + 1; ++j)
        {
            int section = water_sum[i + h - 1][j + w - 1] - water_sum[i + h - 1][j - 1] - water_sum[i - 1][j + w - 1]
                + water_sum[i - 1][j - 1];

            if (section == 0)
            {
                answer++;
            }
        }
    }

    cout << answer;

    return 0;
}