16236번 아기 상어

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

저번에 푼 코드 : http://hsdevelopment.tistory.com/114

SW 역량 테스트 대비할 겸, 다시 풀어보았다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct babyshark
{
    int Size;
    int eat;
    int y;
    int x;
    int time;
}babyshark;
 
babyshark bs;
 
// 왼쪽, 위쪽부터.
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int N = 0;
 
int Map[22][22] = { 0, };
 
bool cmp(const pair< pair<int, int>, int> & a, const pair< pair<int, int>, int> & b)
{
    // 거리 우선
    if (a.second == b.second)
    {
        // 행이 같다면, 가장 왼쪽에 있는 것부터
        if (a.first.first == b.first.first) return a.first.second < b.first.second;
        else return a.first.first < b.first.first;
    }
    else return a.second < b.second;
}
 
void BFS()
{
    while (1)
    {
        queue<pair<int, int> > q;
 
        bool visit[22][22] = { false, };
 
        q.push({ bs.y, bs.x });
 
        visit[bs.y][bs.x] = true;
 
        vector<pair< pair<int, int>, int> > v;
 
        int ret = 0;
 
        while (!q.empty())
        {
            int qSize = q.size();
 
            while (qSize--)
            {
                int r = q.front().first;
                int c = q.front().second;
 
                q.pop();
 
                if (Map[r][c] != 0 && bs.Size > Map[r][c])
                {
                    v.push_back({ { r, c }, ret });
                }
 
                for (int i = 0; i < 4; i++)
                {
                    int y = r + dy[i];
                    int x = c + dx[i];
 
                    // 자신의 크기보다 더 큰 물고기가 있는 위치를 지나갈 수 없다.
                    if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || bs.Size < Map[y][x]) continue;
 
                    q.push({ y, x });
                    visit[y][x] = true;
                }
            }
 
            ++ret;
        }
 
        if (v.empty()) return;
 
        if (v.size() > 1) sort(v.begin(), v.end(), cmp);
 
        bs.y = v.at(0).first.first; // 먹을 물고기 위치를 아기 상어의 위치로
        bs.x = v.at(0).first.second;
 
        bs.time += v.at(0).second; // 출발 지점에서 먹을 물고기로 가는데 걸리는 시간
        
        ++bs.eat; // 물고기를 먹고
 
        Map[bs.y][bs.x] = 0; // 먹은 물고기 처리
 
        if (bs.Size == bs.eat) // 근데 먹은 물고기 수가 아기 상어의 크기와 같다면
        {
            ++bs.Size; // 사이즈 증가
            bs.eat = 0; // 다시 먹은 물고기 수는 0으로
        }        
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) 
    {
        for (int j = 0; j < N; j++) 
        { 
            scanf("%d", &Map[i][j]); 
 
            if (Map[i][j] == 9)
            {
                bs.eat = 0;
                bs.Size = 2; // 아기 상어 처음 크기
                bs.y = i;
                bs.x = j;
                bs.time = 0;
 
                Map[i][j] = 0;
            }
        }
    }
 
    BFS();
 
    printf("%d\n", bs.time);
 
    return 0;
}