[백준 16236] 아기 상어

BFS + 시뮬레이션 문제임

 

BFS 탐색했을때 가장 먼저 나오는 물고기를 먹으면 안됨.

반례가 존재함.

먹을 수 있는 물고기 모두 찾은 다음, 정렬 통해서 먹을 물고기 구해야함

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <bitset>
#include <cmath>

#define SIZE 21

using namespace std;

int N, L, R;
int map[SIZE][SIZE];
// 상어가 가장 위 왼쪽부터 탐색할 수 있도록
int dy[4] = {-1, 0, 0, 1};
int dx[4] = {0, -1, 1, 0};
int shark = 2;
int eat = 0;
int sharky, sharkx;

struct comp
{
    bool operator()(const tuple<int, int, int> &a, const tuple<int, int, int> &b)
    {
        auto [a1, a2, a3] = a;
        auto [b1, b2, b3] = b;

        // a3가 클수록 우선순위 낮음
        if (a3 != b3)
            return a3 > b3;
        // a1이 클수록 우선순위 낮음
        if (a1 != b1)
            return a1 > b1;
        // a2가 클수록 우선순위 낮음
        return a2 > b2;
    }
};

int solve()
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, comp> pq;

    queue<tuple<int, int, int>> q;
    bitset<SIZE> visited[SIZE];
    q.push({sharky, sharkx, 0});
    visited[sharky][sharkx] = 1;

    while (!q.empty())
    {
        auto [y, x, dist] = q.front();
        q.pop();

        int newy, newx;
        for (int i = 0; i < 4; i++)
        {
            newy = y + dy[i];
            newx = x + dx[i];

            if (newy < 0 || newx < 0 || newy >= N || newx >= N)
            {
                continue;
            }

            // 아직 방문하지 않고
            // 자기보다 크지 않은 물고기가 있는 칸이면 방문
            if (!visited[newy][newx] && map[newy][newx] <= shark)
            {
                visited[newy][newx] = 1;
                q.push({newy, newx, dist + 1});

                // 빈칸이 아닌 물고기 칸이면 기록해두기
                if (map[newy][newx] != 0 && map[newy][newx] < shark)
                {
                    pq.push({newy, newx, dist + 1});
                }
            }
        }
    }

    // 잡아먹을 수 있는 물고기가 없다면
    if (pq.empty())
    {
        return 0;
    }

    auto [nexty, nextx, cost] = pq.top();

    // 잡아먹기
    map[nexty][nextx] = 0;
    // 잡아먹은 물고기 갯수
    eat++;
    // 자신의 크기만큼 잡아먹었으면 성장
    if (eat == shark)
    {
        shark++;
        eat = 0;
    }

    // 상어 시작점 최신화
    sharky = nexty;
    sharkx = nextx;

    // 이동거리 반환
    return cost;
}

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

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            cin >> map[i][k];
            if (map[i][k] == 9)
            {
                map[i][k] = 0;
                sharky = i;
                sharkx = k;
            }
        }
    }

    int total = 0;
    while (1)
    {
        int cnt = solve();
        if (cnt == 0)
            break;
        total += cnt;
    }

    cout << total;
    return 0;
}