[BOJ] 아기 상어

[BOJ] 아기 상어

Problem URL : 아기 상어

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#define p pair<int,int>

using namespace std;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int n;
int ans;

int map[20][20];
int visit[20][20];

struct Shark {
    int x;
    int y;
    int size;
    int eat;
    Shark() {};
    Shark(int a, int b, int c, int d) : x(a), y(b), size(c), eat(d) {};
};

bool inRange(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}

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

    cin >> n;
    Shark shark;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) {
                map[i][j] = 0;
                shark.x = i;
                shark.y = j;
                shark.size = 2;
                shark.eat = 0;
            }
        }
    }

    while (1) {
        memset(visit, 0, sizeof(visit));
        vector<pair<int, pair<int, int> > > fish;

        queue< pair<int, pair<int, int> > > q;
        q.push({ 0,p(shark.x, shark.y) });
        visit[shark.x][shark.y] = 1;

        while (!q.empty()) {
            int x = q.front().second.first;
            int y = q.front().second.second;
            int time = q.front().first;
            q.pop();
            time++;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (!inRange(nx, ny)) continue;
                if (visit[nx][ny]) continue;
                visit[nx][ny] = 1;
                if (map[nx][ny] > shark.size) continue;
                if (1 <= map[nx][ny] && map[nx][ny] < shark.size) {
                    fish.push_back({ time, p(nx, ny) });
                }

                q.push({ time ,p(nx, ny) });
            }
        }

        if (fish.size() == 0) {
            break;
        }

        sort(fish.begin(), fish.end());

        int time = fish.front().first;
        int x = fish.front().second.first;
        int y = fish.front().second.second;

        ans += time;
        map[x][y] = 0;
        shark.x = x;
        shark.y = y;

        shark.eat++;
        if (shark.size == shark.eat) {
            shark.size++;
            shark.eat = 0;
        }
    }
    cout << ans << endl;
    return 0;
}