[백준 16236번] 아기 상어 (C++)

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

16236번: 아기 상어

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N;
int arr[20][20];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

struct Info
{
    int y, x, dist;
};

struct Cmp{
    bool operator()(const Info &a, const Info &b)
    {
        if (a.dist == b.dist)  //거리가 같다면 가장 위에 있는 물고기
        {
            if (a.y == b.y) 
                return a.x > b.x; //그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기
            return a.y > b.y;
        }
        return a.dist > b.dist;
    }
};

queue<Info> q;

int bfs()
{
    int size = 2, cnt = 0, yummy = 0; //아기상어 사이즈, 총 시간, 먹은 횟수

    while (true)
    {
        priority_queue<Info, vector<Info>, Cmp> fish; //거리가 제일 가까운 순
        vector<vector<bool>> visit(N, vector<bool>(N, 0)); //2차원 벡터
        while (!q.empty())
        {
            Info cur = q.front();
            q.pop();

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

                if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                if (visit[ny][nx] || arr[ny][nx] > size) continue;

                visit[ny][nx] = 1;

                q.push({ny, nx, cur.dist + 1}); //거리 저장

                if (arr[ny][nx] < size && arr[ny][nx] != 0) //먹었다면
                {
                    fish.push({ny, nx, cur.dist + 1}); //먹은 거리 저장
                }
            }
        }

        if (fish.empty()) break;
        Info fcur = fish.top();
        int fishY = fcur.y, fishX = fcur.x;

        yummy++; //먹은 횟수 증가

        if (yummy == size) //횟수랑 사이즈가 같다면
        {
            yummy = 0;
            size++;
        }

        arr[fishY][fishX] = 0; //먹어서 없어짐
        q.push({fishY, fishX, 0}); //먹은 곳부터 다시 카운트

        cnt += fcur.dist; //먹이까지 간 거리 저장
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 9)
            {
                arr[i][j] = 0;
                q.push({i, j, 0});
            }
        }

    cout << bfs();

    return 0;
}

bfs의 응용문제이다.

푸는데 애먹어서 검색을 참고했다.

 

단순히 거리를 저장하는 큐와,

먹이까지 간 거리를 저장하는 우선순위 큐를 이용한다.

예제에서 거리가 가까운 순으로, 거리가 같다면 위, 위도 같다면 좌측부터 먹으라고 제시되었다.

 

계속 탐색하며 거리를 늘려가다가 현재 먹이값이 size 값보다 작다면 먹이를 먹고 이때 좌표와 거리를 먹이 큐에 전달한다.

그러고 나서 큐가 종료되면 먹은 횟수를 증가시키고, 이때 먹은 횟수와 사이즈가 같다면 먹은 횟수르 초기화 해줌과 동시에 사이즈를 증가시킨다.

먹이를 먹었다면 해당 값은 0으로 만들고, 현재 좌표와 거리를 넣고 다시 카운트를 시작한다.

그리고 현재 거리가 시간이랑 같으므로 현재 거리를 저장한다.

 

먹이 큐가 비었다면 더 이상 먹을 수 있다는 것이 없다는 것이므로 종료한다.