[BOJ 16236] 아기 상어 (C++)

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

16236번: 아기 상어

 

#include <bits/stdc++.h>

using namespace std;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int space[20][20];
int minVal=987654321;

class Pos{
    public:
    int y;
    int x;
    int cnt;
    Pos(int y, int x, int cnt){
        this->y=y;
        this->x=x;
        this->cnt=cnt;
    }
};

pair<int,int> bfs(int shark_y, int shark_x, int shark_size, int N){
    bool visited[N][N];
    queue<Pos> q;
    pair<int,int> d=make_pair(30,30);
    minVal=987654321;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            visited[i][j]=false;
        }
    }
    q.push(Pos(shark_y, shark_x, 0));
    visited[shark_y][shark_x]=true;
    while (!q.empty()){
        Pos p=q.front();
        q.pop();
        for (int i=0; i<4; i++){
            int ny=p.y+dy[i];
            int nx=p.x+dx[i];
            if (nx<0 || ny<0 || nx>=N || ny>=N){
                continue;
            }
            if ((space[ny][nx]==0 || space[ny][nx]==shark_size) && visited[ny][nx]==false){
                visited[ny][nx]=true;
                q.push(Pos(ny,nx,p.cnt+1));     //이동할 수 있으면 탐색 
            }
            else if (space[ny][nx]>=1 && space[ny][nx]<shark_size && visited[ny][nx]==false){       //먹을 수 있는 물고기이면 pq에 넣음
                visited[ny][nx]=true;
                if (p.cnt+1<minVal){
                    minVal=p.cnt+1;
                    d.first=ny;
                    d.second=nx;
                }
                else if (p.cnt+1==minVal){
                    if (ny<d.first){
                        d.first=ny;
                        d.second=nx;
                    }
                    else if (ny==d.first){
                        if (nx<d.second){
                            d.first=ny;
                            d.second=nx;
                        }
                    }
                }
            }
        }
    }
    return d;
}

int main(){
    int N, x;
    int answer=0;
    int num=0;         
    cin>>N;
    int shark_y, shark_x;
    int shark_size=2;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cin>>x;
            space[i][j]=x;
            if (x==9){
                shark_y=i;
                shark_x=j;
            }
        }
    }
    while (true){
        pair<int,int> p=bfs(shark_y, shark_x, shark_size, N);
        if (p.first==30){
            break;
        }
        space[shark_y][shark_x]=0;  //기존에 있던 곳 0으로 
        shark_y=p.first;
        shark_x=p.second;
        num++;
        if (num==shark_size){
            shark_size+=1;
            num=0;
        }
        space[shark_y][shark_x]=0;
        answer+=minVal;
    }
    cout<<answer<<"\n";
    return 0;
}

비효율적으로 푼듯..

 

일단, bfs 로 탐색하다가 이동할 수 있으면=>계속 큐에 넣어서 이동한다.

만약 아기상어가 먹을 수 있는 것이면 => minValue와 비교하고, minValue 와 같을 경우에는 가장 위에, 가장 왼쪽에 있는 애를 반환하도록 한다. 

탐색이 끝나고 큐가 종료되면 아기상어가 먹은 자리를 0으로 해주고, 아기상어의 자리를 갱신해주고 또 bfs 를 돌리는 식이다.

반복문의 종료는 bfs 함수가 더이상 새로운 좌표를 반환하지 않았을 때 종료한다.

 

그런데 이렇게 하니까 따져줘야 될 것도 번거롭게 많다..

 

https://rebas.kr/714

BOJ 16236 · 아기 상어

이 분의 코드를 참고하니,

priority_queue 를 사용해서 이동할 수 있는 애들을 큐에 모두 다 집어넣어준다.

(미방문이고, 아기 상어의 크기보다 작은 애들이거나 0 인 애들)

priority_queue 는 우선적으로 count가 작은 애들이고, count 가 같을 경우엔 가장 위, 가장 왼쪽에 있는 애들이 큐의 앞쪽에 위치한다.

이렇게 하면 자동적으로 조건에 맞는 아기상어의 먹이가 튀어나올 수 있다.

큐에서 아이템을 하나뺄때는, 아기상어의 먹이가 될 수 있는 것이면(0을 초과 하고, 아기상어의 크기보다 작은) 그 위치에 0 처리를 해주고, 크기 조건을 만족하면 크기를 늘려주고, 이제 이 priority_queue 에 대해서는 탐색을 하지 않아도 되므로(먹이를 찾았으니 이제 새롭게 움직여야하니) 큐를 모두 비워주고, 이 새로운 위치에 대해서 다시 bfs 탐색을 하는 식이다!!

 

struct a{

int d, x,y;

bool operator < (const a &t) const{

...

}

}; 

이런 식으로 구현해주고, 큐에는 q.push({1,2,3}) 이런 식으로 넣어주면 자동적으로 min-heap 구조로 아이템이 튀어나오게 된다.

 

내 코드는 아기상어의 먹이를 찾았더라도 혹시 모를 또다른 최소값을 위해 계속 bfs 를 돌린다.. 비효율적이다.. 시간초과는 나지 않았지만 말이다.

핵심은, 우선순위 큐를 이용한 BFS 를 이용해, 바로 조건에 맞는 먹이가 튀어나오도록 하며 그 먹이가 나왔을 때는 그걸 기준으로 다시 bfs 를 돌린다는 것!