[백준 16236] 아기상어 (BFS) (C/C++) (★★★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int size;
    int eat;
    int dist;
}node;
 
int map[21][21];
int N;
int ans;
 
queue<node> q;
int visited[21][21];
 
node f;
vector<node> fish;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
bool cmp(node A, node B)
{
    // 거리가 같을 경우
    if(A.dist == B.dist)
    {
        // 위쪽에 있는 먹이가 여러개인 경우
        if(A.x == B.x)
        {
            // 왼쪽에 있는 먹이
            if(A.y < B.y)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        // 위쪽에 있는 먹이 
        else if(A.x < B.x)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    // 가장 짧은 거리 
    else if(A.dist < B.dist)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    while(1)
    {
        memset(visited, 0, sizeof(visited));
        fish.clear();
        
        visited[f.x][f.y] = 1;
        q.push(f);
        
        // 먹이가 될수있는 물고기를 찾는 반복문 
        while(!q.empty())
        {
            int x = q.front().x;
            int y = q.front().y;
            int size = q.front().size;
            int eat = q.front().eat;
            int dist = q.front().dist;
            q.pop();
            
            for(int i = 0; i < 4; i++)
            {
                int xpos = x+dx[i];
                int ypos = y+dy[i];
                
                // 먹이 없이 지나갈수만 있는 경우 
                if(safe(xpos, ypos) == 1 && (map[xpos][ypos] == 0 || map[xpos][ypos] == 9 || map[xpos][ypos] == size) && visited[xpos][ypos] == 0)
                {
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos, size, eat, dist+1});
                }
                // 먹이가 있는 경우 
                else if(safe(xpos, ypos) == 1 && map[xpos][ypos] < size && visited[xpos][ypos] == 0)
                {
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos, size, eat, dist+1});
                    
                    // 먹이가 될수 있는 물고기 저장 
                    fish.push_back({xpos, ypos, size, eat, dist+1});
                }
            }
        }
        
        // 먹이가 될 수 있는 물고기가 없으면 종료 
        if(fish.size() == 0)
        {
            return;
        }
        
        sort(fish.begin(), fish.end(), cmp);
        
        // 물고기를 잡아먹음 
        fish[0].eat++;
        
        // 상어의 크기 = 잡아먹은 물고기 수  
        if(fish[0].size == fish[0].eat)
        {
            fish[0].size++;
            fish[0].eat = 0;
        }
        
        // 잡아 먹은 물고기 지움
        map[fish[0].x][fish[0].y] = 0;
        
        // 움직인 거리 저장
        ans += fish[0].dist;
        
        // f 초기화
        f = {fish[0].x, fish[0].y, fish[0].size, fish[0].eat, 0}; 
    }
}
 
int main(void)
{
//    freopen("B16236_input.txt", "r", stdin);
    
    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)
            {
                f = {i, j, 2, 0, 0};
            }
        }
    }
    
    BFS();
    
    cout << ans; 
 
    return 0;
}