(C++) 백준 16236 아기 상어

문제 및 풀이

https://www.acmicpc.net/problem/16236
그래프 문제 ,,

• 처음에 시간초과 났는데 큐에 먼저 넣은 후 처리 전에 방문여부 확인하는게 아니라 큐에 넣기 전에 방문여부 확인해야 함 ㅠ 항상 확인하고 하자
• 처음에는 단순 dfs라고 생각해서 탐색했는데 (위, 왼쪽 순으로...) 이 과정에서 무조건 우선순위대로 입력되지 않는다! 예를들어 length=1일때 위, 왼쪽이어도 그 다음 큐에 들어가는 경우(length=2) 아래, 위 이런순으로 바뀌어서 들어갈 수 있다..
  따라서 우선순위큐를 사용해서 같은 거리의 먹을 수 있는 먹이들 중 가장 가까운 먹이를 찾야아 한다

이런 구현문제 무조건 struct 로 접근해야지 아니면 못푸는거같다 ㅠㅠ
struct 생성자 구현 / 연산자 오버로딩 항상 주의하고 기억하자 ~

코드

#include <iostream>
#include <queue>
using namespace std;


int arr[25][25];
bool isvisited[25][25];
int N;

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

int SIZE=2;
int level;
int ans;

struct nextPos{
    int y; int x; int cnt;
    nextPos(int y, int x, int cnt) : y(y), x(x), cnt(cnt) {};

};


struct cmp{
    bool operator()(pair<int, int> &a, pair<int, int> &b){
        if(a.first==b.first) return a.second>b.second;
        else return a.first>b.first;
        }
};



pair<int, int> findBabyShark(){
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(arr[i][j]==9) return {i,j};
}


int findFish(int y, int x){

    for(int i=0; i<N; i++) for(int j=0; j<N; j++) isvisited[i][j]=false;

    queue<nextPos> q;
    q.push({y,x,1});
    priority_queue<pair<int ,int>, vector<pair<int, int>>, cmp> pq;
    int memo=-1;
    isvisited[y][x]=true;

    while(!q.empty()){
        int yy = q.front().y;
        int xx = q.front().x;
        int cnt = q.front().cnt;
        q.pop();


        for(int k=0; k<4; k++){

            int ny = yy + dy[k];
            int nx = xx + dx[k];

            if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
            if(arr[ny][nx]>SIZE || isvisited[ny][nx]) continue;

            isvisited[ny][nx]=true;

            if(arr[ny][nx]==0 || arr[ny][nx]==SIZE) {
                q.push({ny,nx,cnt+1});
                continue;
            }

            if(memo==-1 || memo==cnt) {
                memo=cnt;
                pq.push({ny,nx});
            }
            else continue;
        }

    }

    if(!pq.empty()){
        int ty = pq.top().first;
        int tx = pq.top().second;

        ans += memo;
        arr[y][x]=0;
        int tmp = arr[ty][tx];
        arr[ty][tx]=9;
        return tmp;
    }

    return -1;
}



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);


    cin>>N;

    int start_x, start_y;

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin>>arr[i][j];
        }
    }


    while(1){

        pair<int,int> pos= findBabyShark();
        start_y= pos.first;
        start_x = pos.second;
        int tmp = findFish(start_y, start_x);


        //cout<<start_y<<" "<<start_x<<" "<<size<<" "<<level<<'\n';
        if(tmp==-1) break;
        if(tmp!=0 && tmp<SIZE){
            level++;
        }
        if(level==SIZE){
            SIZE++;
            level=0;
        }


    }

    cout<<ans;
}