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

문제

접근 방법

우선순위가 가장 높은 물고기를 찾는 것이 목표이다.
현재 아기 상어의 위치에서 BFS를 통해 닿을 수 있는 물고기를 찾는다. 만약 0이거나 크기가 같다면 탐색할 수 있는 지점인 것이다.
이후 조건에 맞는 물고기를 찾아 이동해 주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int, int>;
using piii = pair<int, pii>;
vector<vector<int>> map;
vector<vector<bool>> isVisited;
pii curPos;
piii nextPos;
int N, curSize = 2, time, cnt;
int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    isVisited = vector<vector<bool>>(N, vector<bool>(N));
    map = vector<vector<int>>(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> map[i][j];
            if (map[i][j] == 9) // 시작
            {
                map[i][j] = 0;
                curPos = {i, j};
            }
        }
    }
}
void find()
{
    nextPos = {400, {20, 20}};
    queue<piii> q;
    q.push({0, curPos});
    isVisited[curPos.first][curPos.second] = true;
    while (!q.empty())
    {
        piii cur = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cur.second.first + dy[i];
            int nx = cur.second.second + dx[i];
            piii next = {cur.first + 1, {ny, nx}};

            if (ny < 0 || nx < 0 || ny >= N || nx >= N || isVisited[ny][nx]) // 범위를 벗어났거나 이미 방문했다면
            {
                continue;
            }
            isVisited[ny][nx] = true;

            if (map[ny][nx] == 0 || map[ny][nx] == curSize) // 비어있거나 크기가 같다면
            {
                q.push(next);
            }
            else if (map[ny][nx] < curSize) // 아기 상어보다 작다면
            {
                if (next.first < nextPos.first) // 다른 물고기보다 거리가 가깝다면
                {
                    nextPos = next;
                }
                else if (next.first == nextPos.first)
                {
                    if (next.second.first < nextPos.second.first) // 다른 물고기보다 위에 있다면
                    {
                        nextPos = next;
                    }
                    else if (next.second.first == nextPos.second.first)
                    {
                        if (next.second.second < nextPos.second.second) // 다른 물고기보다 왼쪽에 있다면
                        {
                            nextPos = next;
                        }
                    }
                }
            }
        }
    }
}
void solve()
{
    while (true)
    {
        find();

        if (nextPos.first == 400) // 못 찾았다면
        {
            break;
        }

        ++cnt;
        if (cnt == curSize) // 크기만큼 물고기를 먹었다면
        {
            ++curSize;
            cnt = 0;
        }
        time += nextPos.first;
        map[nextPos.second.first][nextPos.second.second] = 0;
        curPos = nextPos.second;

        fill(isVisited.begin(), isVisited.end(), vector<bool>(N));
    }
    cout << time;
}
int main()
{
    input();
    solve();
    return 0;
}

풀이

비어있거나 아기 상어와 같은 크기의 물고기는 탐색할 수 있는 칸인 것이다. 만약 탐색할 수 없다면 아기 상어보다 작은 크기의 물고기인지 확인한다.

이후 아기 상어보다 크기가 작다면 우선순위에 해당하는지 확인하고 우선순위에 해당하면 갱신해 준다. 갱신된 물고기까지 이동해 주고 다음 물고기를 찾는 것을 반복해 주면 된다.

N의 크기가 최대 20이기에 매 순간 BFS로 먹을 수 있는 물고기의 위치를 찾아주어도 큰 무리가 되지 않는다.