[BOJ] 16236 아기 상어

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

16236번: 아기 상어

처음에 bfs를 왼쪽, 위, 오른쪽, 아래 방향으로 우선 순위를 줘서 탐색하면 해결 될 줄 알았다.

하지만 이렇게 bfs를 구현할 경우 탐색 순서는 다음과 같다.

따라서 나는 우선순위 큐 stl을 이용하여 거리 > y값이 작은 좌표 > x값이 작은 좌표 순를 우선순위로 정렬한 다음 bfs를 이용하여 문제를 풀었다. 조심해야 할 점은 pop을 할 때 조건을 만족하는지 검사해야 한다는 것이다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define endl '\n'
#define ll long long

using namespace std;

int dx[]={0,-1,1,0};
int dy[]={-1,0,0,1};

int N;
int map_[20][20];

bool visit[20][20];
int pos_y,pos_x;
int shark_size=2;
int eat_cnt=0;

//우선 순위 : 거리 > y좌표가 작은 것 > x 좌표가 작은 것
struct cmp{
    bool operator()(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;
        }
        return a.second>b.second;
    }
};

void input(){
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>map_[i][j];
            if(map_[i][j]==9){
                map_[i][j]=0;
                pos_y=i;
                pos_x=j;
            }
        }
    }
}

void init() {
}

int bfs(){
    int time=1;
    // bfs를 돌 때마다 visit값을 초기화 시켜야 한다.
    fill(&visit[0][0],&visit[19][20],false);
    
    priority_queue<pair<pair<int,int>,int>, vector<pair<pair<int,int>,int> >, cmp > q;
    q.push(make_pair(make_pair(pos_y,pos_x),0));
    visit[pos_y][pos_x]=true;
    
    while(!q.empty()){
        int y=q.top().first.first, x=q.top().first.second,dist=q.top().second; q.pop();
        
        //목표에 도착했는지 확인한다.
        if(map_[y][x]!=0&&map_[y][x]<shark_size){
            if(++eat_cnt==shark_size){
                shark_size++;
                eat_cnt=0;
            }
            //상어가 먹은 곳은 빈칸 처리를 해줘야 한다.
            pos_y=y,pos_x=x,map_[y][x]=0;
            return dist;
        }
        
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(0<=ny&&ny<N&&0<=nx&&nx<N&&!visit[ny][nx]){
                if(map_[ny][nx]==0||map_[ny][nx]<=shark_size){
                    visit[ny][nx]=true;
                    q.push(make_pair(make_pair(ny,nx),dist+1));
                }
            }
        }
    }
    
    return 0;
}

int solution() {
    int ans=0;
    while(1){
        int tmp=bfs();
        if(tmp==0) break;
        ans+=tmp;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    cout<<solution();
    return 0;
}