16236 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/16236.cpp

코드를 한 번 짜긴 했는데 너무 더러워서 해설 코드를 참고했다. 무난한 문제였다고 생각한다.

#include <bits/stdc++.h>
using namespace std;

int board[23][23];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int n,ans;
int shY,shX;
int shSize=2, fishCnt=0; //상어크기 먹은먹이개수
int dist[23][23];

tuple<int,int,int> bfs(int y, int x){
    tuple<int,int,int> mn={0x7fffffff,0x7fffffff,0x7fffffff}; //dist y x
    queue<pair<int,int>> Q;
    Q.push({y,x});
    for(int i=0;i<n;i++)
        fill(dist[i],dist[i]+n,-1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(board[i][j]==9){
                board[i][j]=0;
                dist[i][j]=0;
            }
        }
    }
    while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        int curY,curX; tie(curY,curX)=cur;
        if(dist[curY][curX]>=get<0>(mn)) break;
        for(int dir=0;dir<4;dir++){
            int ny=curY+dy[dir];
            int nx=curX+dx[dir];
            if(ny<0||nx<0||nx>=n||ny>=n) continue;
            if(dist[ny][nx]!=-1 || board[ny][nx]>shSize) continue;
            dist[ny][nx]=dist[curY][curX]+1;
            if(board[ny][nx]<shSize && board[ny][nx]!=0) mn=min(mn,{dist[ny][nx],ny,nx});
            Q.push({ny,nx});
        }
    }
    return mn;
}

int main(void) {
	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>>board[i][j];
            if(board[i][j]==9){
                shY = i;
                shX = j;
            }
        }
    }
    while(true){
        auto mn=bfs(shY,shX);
        int curD,curY,curX; tie(curD,curY,curX)=mn;
        if(curD==0x7fffffff) break;
        fishCnt++;
        if(fishCnt==shSize){
            shSize++; fishCnt=0;
        }
        shY=curY; shX=curX;
        board[shY][shX]=9;
        ans+=curD;
    }
    cout<<ans;
	return 0;
}