백준 16236 아기상어

아기 상어

아기 상어가 먹이를 먹으면 크기가 커지는데, 상어가 물고기를 잡아먹을 수 있는 시간을 출력하는 문제.

문제분석

첫째, 먹을 수 있는 가장 가까운 물고기를 먹으러 간다.

현재 아기 상어의 위치에서 bfs 탐색을 통해 먹을 수 있는 최단거리 물고기를 구한다.

둘째, 물고기가 1마리 이상이라면, 가장 위 -> 가장 왼쪽에 있는 물고기를 구한다.

bfs 탐색의 특징중 최단거리가 여러개면 그때마다 벡터에 값을 추가할 수 있으므로 정답 조건을 만족할 때마다 정답에 추가한 뒤에, bfs함수 마지막에 정답 배열(vector<tuple<정답,행,열»)을 정렬하면, 정답, 행, 열 순으로 정렬될 것이다.

셋째, 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가하므로 크기를 매번 바꾸어준다

bfs함수가 한번 끝날 때 마다, 정답배열이 비어있으면 -1을 return해주고, -1이 아니면 정답이 존재하는 것이므로, 상어가 한번 먹었다고 처리해주고, 먹은 물고기의 개수가 상어의 크기가 같으면 상어의 크기가 한번 증가한다고 처리해준다.

go함수를 n^2번 실행한 이유는 물고기가 모든 칸에 있다고 가정했기 때문이다.
(상어의 처음 위치를 빼면 n^2-1).

오타나 질문, 지적 환영입니다.

소스

#include<iostream>
#include<bits/stdc++.h>

using namespace std;
int ma[100][100];
int x_index[4]={-1,0,0,1};
int y_index[4]={0,-1,1,0};
int n;
int shark=2;
int s_exp=0;
tuple<int,int,int> go(int x,int y){ //아기상어의 위치

    int ans=0;
    int d[21][21]={0};
    queue<tuple<int,int,int>> q;
    q.push(make_tuple(0,x,y));
    vector<tuple<int,int,int>> ansv;
    while(!q.empty()){
        tie(d[x][y],x,y)=q.front();q.pop();
        int nx,ny;
        for(int i=0;i<4;i++){
            nx=x+x_index[i];
            ny=y+y_index[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n)
                continue;
            if(ma[nx][ny]>shark || d[nx][ny]>0)
                continue;
            if(ma[nx][ny]==0 || ma[nx][ny]==shark){
                d[nx][ny]=d[x][y]+1;
                q.push(make_tuple(d[nx][ny],nx,ny));
            }
            if(ma[nx][ny]<shark && ma[nx][ny]!=0){
                ans=d[x][y]+1;
                ansv.push_back(make_tuple(ans,nx,ny));
            }
            
        }
    }
    if(ansv.empty()){
        return make_tuple(-1,-1,-1);
    }
    sort(ansv.begin(), ansv.end());
    return ansv[0];
    
}

int main(){
    cin>>n;
    int x,y;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>ma[i][j];
            if(ma[i][j]==9){
                x=i;
                y=j;
                ma[i][j]=0;
            }
        }
    }
    int ans=0;
    int tmp=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            tie(tmp,x,y)=go(x,y);
            if(x==-1 || y==-1 || tmp==-1)
                break;
            ma[x][y]=0;
            s_exp++;
            if(s_exp==shark)
            {
                shark++;
                s_exp=0;
            }
            ans+=tmp;
        }
    }
    cout<<ans<<'\n';

}