[Baekjoon][16236] 아기 상어

출처 - 백준사이트

16236. 아기 상어

나의 풀이

이 문제풀때, 머리속에 "아기상어 뚜루루뚜룻~" 노래가 맴도는 순간 집중력 흐트러지니 주의

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

#define MAX_SIZE    20

using namespace std;

typedef struct _shark {
    int y;
    int x;
} Shark;

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

int N;
int map[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE] = {false, };
int movingtime, sharkSize, sizeupCnt;
int result;
Shark shark;

void Moving(void) {
    queue<Shark> q;

    q.push(shark);

    bool isUpdate = true;
    while (isUpdate) {
        isUpdate = false;

        queue<Shark> cur;
        cur.push(q.front()); q.pop();    // 상어가 이동한 뒤 (업데이트 이후) 처음위치.

        while (!cur.empty()) {
            int cycle = cur.size();

            for (int n=0 ; n<cycle ; n++) {        // 지금 큐에 담겨있는 만큼만 돈다.
                Shark temp = cur.front(); cur.pop();

                for (int i=0 ; i<4 ; i++) {
                    int ny = temp.y + dy[i];
                    int nx = temp.x + dx[i];

                    if ( ny>=0 && ny<N && nx>=0 && nx<N && (visited[ny][nx]==false) && (map[ny][nx]<=sharkSize)) { // 맵을 넘어가지 않고 방문안했고, 현재 크기보다 작거나 같은 움직임.
                        Shark next = {ny,nx};
                        visited[ny][nx] = true;

                        if ((map[ny][nx]<sharkSize) && (map[ny][nx]!=0)) { // 물고기 먹은경우.
                            isUpdate = true;
                            q.push(next);        // 현재 상어 위치를 메인 큐에 저장.
                        }
                        else         // 먹은 경우가 아니면 단순 이동을 위해 이동큐에 저장.
                            cur.push(next);
                    }
                }
            }

            movingtime++; // 한 싸이클 돌았으니 시간 증가.

            if (isUpdate) {        // 물고기를 먹은 경우
                Shark pick = q.front(); q.pop();

                while (!q.empty()) {    // 가장위, 가장왼쪽 위치의 물고기 찾기.
                    Shark temp = q.front(); q.pop();

                    if (temp.y < pick.y || ((temp.y == pick.y) && (temp.x < pick.x)))
                        pick = temp;
                }

                q.push(pick);    // 메인큐에 이동한 상어 위치 저장.

                sizeupCnt++;

                if (sizeupCnt == sharkSize) {
                    sharkSize++;
                    sizeupCnt = 0;
                }

                memset(visited, false, sizeof(visited));
                while(!cur.empty())        // 이동큐는 다 비움.
                    cur.pop();

                map[pick.y][pick.x] = 0;
                visited[pick.y][pick.x] = true;
                result += movingtime;    // 이동한 시간 업데이트.
                movingtime = 0;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> N;

    for (int y=0 ; y<N ; y++) {
        for (int x=0 ; x<N ; x++) {
            cin >> map[y][x];

            if (map[y][x] == 9) {
                map[y][x] = 0;
                visited[y][x] = true;
                shark.x = x;
                shark.y = y;
                sharkSize = 2;
            }
        }
    }

    Moving();
    cout << result;

    return 0;
}