16236 아기 상어

16236 아기 상어 (c++)

문제

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

접근 방식

BFS

1. 아기 상어의 위치에서 각 물고기들까지 BFS
2. 자기보다 작은 물고기 중 거리가 가장 짧고, 가장 윗쪽, 가장 왼쪽의 물고기를 먹는다.
3. 먹은 고기의 숫자가 상어의 크기 숫자와 일치하면 크기 + 1
4. 다시 1번부터 반복

문제 풀이

#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;

int N;
int board[20][20];
int costArr[20][20] = {};
bool visited[20][20] = {};
int startY, startX;
int nowSize = 2;
int nowEat = 0;
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };

// 물고기 정보
int minCost, minY, minX;

void BFS()
{
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            visited[i][j] = false;
            costArr[i][j] = 0;
        }
    }
    minCost = 401;

    queue<pair<pair<int, int>, int>> q;
    q.push({ {startY, startX}, 0 });
    visited[startY][startX] = true;

    while (!q.empty())
    {
        pair<pair<int, int>, int> now = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int nextY = now.first.first + dy[i];
            int nextX = now.first.second + dx[i];
            int nextCost = now.second + 1;

            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) continue;
            if (visited[nextY][nextX] && (costArr[nextY][nextX] <= nextCost)) continue;
            visited[nextY][nextX] = true;
            costArr[nextY][nextX] = nextCost;
            // 그냥 길이라면
            if (!board[nextY][nextX]) q.push({ {nextY, nextX}, nextCost });
            else
            {
                // 물고기인 경우
                // 내 현재 사이즈보다 크다면
                if (board[nextY][nextX] > nowSize) continue;
                else
                {
                    // 내 사이즈보다 작다면
                    if (board[nextY][nextX] < nowSize)
                    {
                        // 가장 가까운지 확인
                        if (minCost > nextCost)
                        {
                            minCost = nextCost;
                            minY = nextY;
                            minX = nextX;
                        }
                        // 거리가 같다면
                        else if (minCost == nextCost)
                        {
                            // 더 윗쪽인지 확인
                            if (minY > nextY)
                            {
                                minY = nextY;
                                minX = nextX;
                            }
                            // Y가 같다면
                            else if (minY == nextY)
                            {
                                // 더 왼쪽인지 확인
                                if (minX > nextX)
                                {
                                    minX = nextX;
                                }
                            }
                        }
                    }

                    q.push({ {nextY, nextX}, nextCost });
                }
            }
        }
    }
}

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

    int answer = 0;

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> board[i][j];
            if (board[i][j] == 9)
            {
                startY = i;
                startX = j;
                board[i][j] = 0;
            }
        }
    }

    while (true)
    {
        BFS();
        if (minCost == 401)
            break;
        answer += minCost;
        startY = minY;
        startX = minX;
        board[startY][startX] = 0;
        nowEat++;
        if (nowEat == nowSize)
        {
            nowEat = 0;
            nowSize++;
        }
    }

    cout << answer << endl;
    

    return 0;
}

다시 생각해볼 점

1. 기본 골자가 아래의 반복이다.
   1. 상어의 현재 위치에서 자신보다 몸집이 작은 가장 가까운 물고기를 먹고 (기준은 위쪽일수록, 같다면 왼쪽일수록)
   2. 먹은 횟수가 사이즈와 같아진다면 사이즈 + 1 해준다.
2. 단순히 상어의 위치와 사이즈가 변하면서 먹을 물고기가 남아 있을 때까지 BFS를 반복해주면 되는 문제였다.