[백준/BOJ] 16236 아기 상어

문제 : 16236 아기 상어

16236번: 아기 상어

상어가 움직이는 조건이 고정되어 있으므로

BFS를 이용해 가장 가까운 물고기를 찾아 이동해 잡아먹는 것을 반복하면 된다.

상어와 여러 물고기의 거리가 같을때 우선순위에 따라 이동하는 것만

잘 설계해주면 크게 어렵지는 않은 문제이다.

---

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9+7
using namespace std;
typedef pair<ll,ll> pll;
struct ABC{
    ll x, y, dst, lv, cnt;
};
ll N, arr[25][25], visited[25][25], ans;
ll dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
ABC shark, fish;
ll scan(){
    fish.dst=INF;
    fill(&visited[0][0],&visited[24][25],-1);
    queue<pll> q;
    q.push({shark.x,shark.y});
    visited[shark.x][shark.y]=0;
    while (!q.empty()){
        ll x=q.front().first, y=q.front().second;
        q.pop();
        for (int i=0;i<4;i++){
            ll dx=x+dir[i][0], dy=y+dir[i][1];
            if (dx<0 || dx>=N || dy<0 || dy>=N)
                continue;
            if (visited[dx][dy]==-1 && arr[dx][dy]<=shark.lv){ // 지나갈 수 있다면
                visited[dx][dy]=visited[x][y]+1;
                q.push({dx,dy});
                if (0<arr[dx][dy] && arr[dx][dy]<shark.lv){ // 잡아먹을수 있다면
                    if (visited[dx][dy]<fish.dst) // 가장 가까운 물고기일때
                        fish.x=dx, fish.y=dy, fish.dst=visited[dx][dy];
                    else if (visited[dx][dy]==fish.dst){
                        if (dx<fish.x || (dx==fish.x && dy<fish.y)) // 가까운 물고기가 여러마리일 때
                            fish.x=dx, fish.y=dy;
                    }
                }
            }
        }
    }
    if (fish.dst==INF) // 먹을수 있는 물고기가 없는 경우
        return 0;
    ans+=fish.dst; // 시간 추가
    shark.x=fish.x;
    shark.y=fish.y;
    shark.cnt++;
    if (shark.cnt==shark.lv){ // 충분한 물고기를 잡아먹었다면 크기 증가
        shark.lv++;
        shark.cnt=0;
    }
    arr[shark.x][shark.y]=0;
    return 1;
}
int main(){
    cin >> N;
    shark.lv=2; // 상어의 크기
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cin >> arr[i][j];
            if (arr[i][j]==9) // 상어의 시작위치
                shark.x=i, shark.y=j, arr[i][j]=0;
        }
    }
    while(scan());
    cout << ans;
    return 0;
}