[BFS] Priority Queue 활용 BFS

일명 물 채우기 BFS 문제

물을 담아두기 위해서, 테두리부터 물을 흘려 보낸다는 아이디어가 필요하다.

 

- 알고리즘

0. 한 번 추가됬던 칸은 check.

1. 테두리를 우선순위 큐에 추가

2. 우선순위 큐에서 하나씩 pop 하면서, 주변 탐색

3. 주변 탐색 시, 더 낮은 높이면 해당 칸으로 나아가 탐색을 진행하고, 아니면 우선순위 큐에 추가

4. 탐색 시에는 처음에 우선순위 큐에서 pop 한 칸의 높이를 기준으로 탐색

 

- 예시 문제

1. 수영장 사장님 : https://www.acmicpc.net/problem/15730

2. 물 채우기 : https://www.acmicpc.net/problem/2276

 

- 수영장 사장님 Code

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int N, M;
int arr[100][100];
int check[100][100];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int answer = 0;
struct yx {
    int y;
    int x;
    int d;
    bool operator<(yx o) const {
        if (d < o.d) return false;
        else if (d > o.d) return true;
        return false;
    }
};
priority_queue<yx> pq;

void bfs(int yy, int xx, int depth)
{
    for (int k = 0; k < 4; ++k)
    {
        int y = dy[k] + yy;
        int x = dx[k] + xx;
        if (x < 0 || y < 0 || x >= M || y >= N || check[y][x]) continue;
        check[y][x] = 1;
        if (arr[y][x] >= depth)
        {
            pq.push({ y, x, arr[y][x]});
        }
        else
        {
            //cout <<depth << ":" << y << x << "\n";
            answer += depth - arr[y][x];
            bfs(y, x, depth);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> arr[i][j];
            if (i == 0 || j == 0 || i == N - 1 || j == M - 1)
            {
                pq.push({ i, j, arr[i][j]});
                check[i][j] = 1;
            }
        }
    }

    while (!pq.empty())
    {
        yx now = pq.top();
        pq.pop();
        bfs(now.y, now.x, now.d);
    }
    cout << answer;
    return 0;
}