[C++/백준] 16236번: 아기 상어*

문제 링크

16236번: 아기 상어

 

풀이

별로 안 어려운 것 같았지만 장장 4시간이나 걸려서 푼 문제...
BFS 문제.. 우선 순위도 잘 파악해야 한다.
처음엔 BFS 한 번 돌려서 풀려고 했지만 한 번 먹을 때마다 상어의 위치를 초기화 해주어야 하고, 거리 > 행 > 열 순으로 물고기를 먹어야 한다....

1. 처음 입력받을 때 아기 상어의 위치가 들어오면 위치를 저장하고 0으로 넣어준다. 나중에 못가는 상황이 생길 수 있음
2. 먹을 수 있는 물고기가 없을 때까지 BFS를 돌린다. 한 번 돌릴 때마다 canEat에 먹을 수 있는 물고기들이 쌓일 것임
3. BFS함수부터 설명하자면, 먼저 상어가 움직일 때마다 시간(나는 거리라고 했다)을 저장하기 위해 dist를 -1로 초기화한다.
   1. 여느 BFS 문제와 같이 queue를 이용하는데, 지나만 갈 수 있는 곳이라면 dist갱신과 q에 push만 해주고,
   2. 먹을 수 있는 물고기가 있다면 dist갱신과 q push에 더불어, canEat vector에 추가해준다.
   3. canEat 벡터는 pair<int, pair<int,int>> 형태라서 거리와 {y,x}가 들어갈 것이다.
   4. q가 빌 때까지 반복한 뒤, 쌓인 canEat를 정렬해준다. 거리, y, x 순으로 넣었기 때문에 커스텀 정렬 필요 없이 바로 거리순, 위쪽에서부터, 왼쪽에서부터로 정렬될 것이다.
   5. 정렬한 canEat를 return한다.
4. canEat의 맨 첫번째 물고기를 먹을 것이다. answer에 dist를 더해주고, 먹었으니 arr[y][x]를 0으로 만들어주고(또 먹으면 안되니), 현재 먹은 물고기 수를 1 더해준다. 이 값 eat가 상어의 사이즈 sharksize보다 크거나 같으면 상어의 사이즈를 +1해주고, eat를 0으로 만들어준다.
5. BFS를 반복하다, 더 이상 먹을 물고기가 없어(canEat.empty()) 엄마 상어를 부른다면 answer를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

vector<pair<int,pair<int,int>>> BFS(vector<vector<int>>& arr, int n, int y, int x, int sharksize)
{
    vector<vector<int>> dist(n, vector<int>(n, -1));
    queue<pair<int,int>> q;

    q.push({ y, x}); // y, x
    dist[y][x] = 0;

    vector<pair<int, pair<int, int>>> canEat; // dist, y, x

    while (!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue; // 범위 밖이라면
            if (dist[ny][nx] >= 0) continue; // 방문했던 곳이라면
            if (arr[ny][nx] > sharksize) continue; // 상어보다 큰 물고기라면
            else if (arr[ny][nx] == sharksize || arr[ny][nx] == 0) // 지나만 갈 수 있는 곳이라면
            {
                dist[ny][nx] = dist[ty][tx] + 1;
                q.push({ ny, nx });
            }
            else // 먹을 수 있다면
            {
                //arr[ny][nx] = 0;
                dist[ny][nx] = dist[ty][tx] + 1;
                canEat.push_back({ dist[ny][nx], {ny, nx} });
                q.push({ ny, nx });
            }
        }
    }

    sort(canEat.begin(), canEat.end());
    return canEat;
}

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

    int n;
    int y, x;

    cin >> n;
    vector<vector<int>> arr(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 9)
            {
                y = i;
                x = j;
                arr[i][j] = 0;
            }
        }
    }

    int sharksize = 2;
    int eat = 0;
    int answer = 0;

    while (true)
    {
        vector<pair<int, pair<int, int>>> canEat = BFS(arr, n, y, x, sharksize);
        if (canEat.empty()) // 먹을 수 있는 물고기가 없다면
        {
            cout << answer;
            return 0;
        }
        else
        {
            int dist = canEat[0].first;
            y = canEat[0].second.first;
            x = canEat[0].second.second;

            answer += dist;
            arr[y][x] = 0; // 먹었으니 0으로

            eat += 1;
            if (sharksize <= eat)
            {
                eat = 0;
                sharksize += 1;
            }
        }
    }
}