[BOJ] 16236. 아기 상어

#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 idx = 1;
int n;
int ans;

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

Gae gae;

struct Fish{
    int value;
    int alive;
    int x;
    int y;
    Fish(){};
    Fish(int a, int b, int c, int d): value(a), alive(b), x(c), y(d) {};
};

Fish fish_map[400];

int map[20][20];

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

p distanse(int idx){
    if(fish_map[idx].value >= gae.size){
        return p(-1,-1);
    }
    
    int visit[20][20] = {0,};
    int time[20][20] = {0,};
    int x = gae.x;
    int y = gae.y;
    int nx = x;
    int ny = y;
    
    queue<p> q;
    q.push(p(x,y));
    visit[x][y] = 1;
    time[x][y] = 1;
    
    while (! q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            
            if(! inRange(nx, ny)) continue;
            if(visit[nx][ny]) continue;
            if( fish_map[ map[nx][ny] ].value > gae.size) continue;
            if( map[nx][ny] == idx){
                return p(time[x][y],idx);
            }
            
            visit[nx][ny] = 1;
            time[nx][ny] = time[x][y] + 1;
            q.push(p(nx,ny));
        }
    }
    return p(-1,-1);
}

void solve(){
    while (1) {
        /*
         우선 순위가
         1. 걸리는 시간
         2. x값
         3. y값 이기 때문에
         [ 시간, x, y ]순서로 넣고
         sort를 하면 front에 있는 값이
         1순위 물고기가 된다.
         */
        vector<pair<int, pair<int,int> > > v;
        
        for(int i=1; i<idx; i++){
            /*
             이미 먹은 물고기에 대해서는 Pass
             */
            if(fish_map[i].alive == 0)
                continue;
            /*
             모든 물고기에 대해 거리를 구한다.
             */
            p res = distanse(i);
            /*
             res.first = -1 && res.second = -1 인 경우는
             1. 개복치의 사이즈보다 물고기가 큰 경우
             2. 개복치의 사이즈랑 같은 물고기인 경우
             그 밖에는 먹을 수 있는 물고기들이다.
             */
            if(res.first != -1 && res.second != -1){
                v.push_back({res.first, {fish_map[res.second].x,fish_map[res.second].y}   });
            }
        } // end of for i
        
        /*
         더 이상 먹을 물고기가 없는 경우
         */
        if(v.size() == 0)
            break;
        /*
         [ 걸리는 시간, x, y ] 우선 순위로 정렬을 실시한다.
         */
        sort(v.begin(), v.end());
        
        int x = v.front().second.first;
        int y = v.front().second.second;
        int t = v.front().first;
        
        ans += t;
        /*
         순서 주의하자.
         map[x][y] = 0 부터 실행하면 안된다.
         */
        fish_map[map[x][y]].alive = 0;
        map[x][y] = 0;
        gae.x = x;
        gae.y = y;
        
        gae.eat ++;
        if(gae.size == gae.eat){
            gae.size ++;
            gae.eat = 0;
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
            /*
             map[i][j]에는 물고기의 Index를 저장한다.
             */
            if(map[i][j] == 9){
                map[i][j] = 0;
                gae.x = i;
                gae.y = j;
                gae.size = 2;
                gae.eat = 0;
            }
            else if(map[i][j] >= 1 && map[i][j] <= 6){
                
                fish_map[idx] = Fish(map[i][j],1,i,j);
                map[i][j] = idx;
                idx++;
            }
        }
    }
    
    solve();
    return 0;
}