[백준] 16236. 아기 상어

아기상어가 물고기를 먹으면서 움직인다.

1. 아기상어가 움직일 수 있는 칸으로 이동하고(BFS사용) 먹을 수 있는 물고기라면 tmp 벡터에 저장한다.

2. tmp 벡터를 이동시간, 위치에 따라 정렬한다.

3. tmp[0]에 있는 물고기를 먹고 아기상어의 위치를 옮긴다.

 

아기 상어의 정보를 따로 저장하였고, 먹은 물고기의 수가 크기와 같아지면 size++를 해주었다. bfs()의 반환값이 0(먹을 물고기가 없을때)이되면 while문을 종료하고 정답을 출력했다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n;
vector<vector<int>> map;
vector<vector<bool>> visit;
vector<vector<pair<int,int>>> fish;
int dxy[4][2] = { {-1,0}, {0,-1},{1,0},{0,1} };
 
struct bs {
    int x, y, size = 2, eat_cnt = 0;
}baby;
struct info {
    int x, y, cnt;
};
 
bool cmp(const pair<pair<int,int>,int> &a, pair<pair<int, int>, int> &b) {
    if (a.second == b.second) {
        if (a.first.first == b.first.first) {
            return a.first.second < b.first.second;
        }
        return a.first.first < b.first.first;
    }
    else
        return a.second < b.second;
 
}
int sec;
int bfs() {
    queue<info> q;
    vector<pair<pair<int, int>, int>> tmp;
    q.push({ baby.x,baby.y,0 });
    visit[baby.x][baby.y] = true;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
 
 
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dxy[i][0];
            int ny = y + dxy[i][1];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (visit[nx][ny]) continue;
            if (map[nx][ny] <= baby.size) {
                visit[nx][ny] = true;
                q.push({ nx,ny,cnt + 1 });
                if (map[nx][ny] != 0 && baby.size > map[nx][ny])
                    tmp.push_back({ { nx,ny },cnt + 1 });
            }
        }
 
 
    }
 
    sort(tmp.begin(), tmp.end(), cmp);
 
    if (!tmp.empty()) {
        int x = tmp[0].first.first;
        int y = tmp[0].first.second;
        baby.eat_cnt++;
        baby.x = x;
        baby.y = y;
        map[x][y] = 0;
        if (baby.eat_cnt == baby.size) {
            baby.size++;
            baby.eat_cnt = 0;
        }
        return tmp[0].second;
    }
 
    return 0;
}
 
int solution() {
    int answer = 0;
    cin >> n;
    baby.size = 2;
    map.assign(n, vector<int>(n));
    fish.assign(7, vector<pair<int, int>>());
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) {
                baby.x = i, baby.y = j;
                map[i][j] = 0;
            }
            if (0 < map[i][j] && map[i][j] <= 6)
                fish[map[i][j]].push_back({ i,j });
        }
    }
    while (true) {
        visit.assign(n, vector<bool>(n, false));
        int tmp = bfs();
        if (tmp == 0) break;
        answer += tmp;
        
    }
    return answer;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    cout<<solution();
    return 0;
}