[백준] 16236번 아기상어 C/C++

//백준 아기상어 16236번

//www.acmicpc.net/problem/16236

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int map[20][20];
int N;
int fishSize = 2, fishCount = 2;
int y, x;
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
bool chk[20][20];
int dist[20][20];
int eaty, eatx;



int simulation() {
    int time = 0;
    memset(dist, 0, sizeof(dist)); //dist 전부 0으로 채우기
    memset(chk, false, sizeof(chk)); //dhk 전부 false으로 채우기,false는 안간거

  
        //초기치 잡아주기
        
        //bfs시작하기전에 기본셋팅 푸시
        queue <pair<int, int>> q;
        q.push({ y,x }); //아기상어 위치 넣
        chk[y][x] = true;//아기상어 위치 true로 변경
        int a = 1;
        while (a) {
            //bfs

            memset(dist, 0, sizeof(dist)); //dist 전부 0으로 채우기
            memset(chk, false, sizeof(chk)); //dhk 전부 false으로 채우기,false는 안간거
            while (!q.empty()) {

                int curY = q.front().first;
                int curX = q.front().second;
                q.pop();

                for (int dir = 0; dir < 4; dir++) {
                    int nextY = curY + dy[dir];
                    int nextX = curX + dx[dir]; //4방향 여기까지 동일

                    //다음에 이동도해야하고, 아직 벽이 아니고,            맵보다 물고기 크기가크면 진행
                    if (nextY < 0 || nextX<0 || nextY >= N || nextX >= N || map[nextY][nextX]>fishSize) continue; //아직 끝나지 않았을때

                    //다음칸안갔고, 아기상어보다 크기도 작아
                    if (!chk[nextY][nextX] && map[nextY][nextX] <= fishSize) { //다음단계넘어가기위해 체크가 필요할때 >> 상어가 먹을꺼야

                        chk[nextY][nextX] = true;
                        dist[nextY][nextX] = dist[curY][curX] + 1;

                        q.push(make_pair(nextY, nextX));
                    }
                }
            }

            //제일 가까운 애 찾기
            int temp_dist = 1000;
            int a = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] != 0 && map[i][j] < fishSize) { //비어있지 않고, 아기상어 크기보다 작으면
                        a = 1; //행동해야해
                        if (dist[i][j] != 0 && dist[i][j] < temp_dist) { //제일 가까운놈만 내마음속에 저장
                            temp_dist = dist[i][j];
                            eaty = i;
                            eatx = j;
                        }
                    }
                }
            }
            if (a == 0) return time;//조건이 나가리면 엄마찾자
            if (temp_dist == 1000) return time; //작은놈없으면 엄마찾자

            fishCount--; //아기상어 몸둥이를 키워보자
            if (fishCount == 0) {
                fishSize++;
                fishCount = fishSize;
            }
            //시간을 누적합니다
            time += temp_dist;
            y = eaty;
            x = eatx;
            map[y][x] = 0;

            q.push(make_pair(y, x));

 
        }
        return time;
}
int main() {

    //입력받기
    scanf_s("%d", &N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf_s("%d", &map[i][j]);
            if (map[i][j] == 9) {//아기상어 위치는 y,x에 저장
                y = i, x = j;
                map[i][j] = 0;
            }
        }
    }
    printf("%d\n", simulation());

    return 0;
 
}