백준 16236번 : 아기 상어(골드 3)

굉장히 요구하는 것이 많았던 구현 + 그래프 문제이다. 문제를 잘 읽어봐야 함

아기 상어가 어떤 위치에 있고 1에서 6까지 크기의 물고기들이 존재한다. 아기 상어의 크기는 2로 시작하고 아기 상어는 주변을 탐지해 제일 가까운 먹을 수 있는 물고기를 찾아서 먹는다

아기 상어는 자기 크기만큼 물고기를 먹으면 크기가 1 증가한다. 예를 들어 크기가 3일때는 물고기 3마리를 먹어야 크기가 4로 증가한다

상어는 자기보다 크기가 큰 물고기는 먹을 수도 없고 지나갈 수도 없다. 크기가 같은 물고기는 먹을 수는 없고 지나갈 수는 있다. 즉 크기가 작은 물고기만 먹을 수 있다

상어가 어떤 물고기와의 거리를 구할 때는 그 사이 물고기를 지나갈 수 있느냐에 따라 거리가 달라진다

상어가 1칸씩 이동할 때마다 1초씩 걸리고 그래서 상어가 물고기를 더 이상 못 먹을때까지의 시간을 구해야 한다

풀이

우선 2차원 배열을 입력받는데 (i, j)에 9가 주어지면 그 곳은 아기 상어의 위치이며 아기 상어의 위치를 처음에 기록해준다

이제 반복문을 통해 상어가 물고기를 잡아먹는 로직을 만들어야 한다

처음에 상어가 먹을 수 있는 물고기 중 가장 가까운 물고기의 위치를 리턴하는 함수를 만들었다

BFS를 통해 현재 상어의 위치부터 시작해 상어가 방문할 수 있는 배열을 채운다. 그래서 어떤 위치로의 최단 거리를 구한다

visited 배열을 완성한 다음, arr 배열을 돌면서 그곳에 물고기가 있고, 물고기의 크기가 상어 크기보다 작고, 상어가 방문한 곳이 어디인지 확인한다

거기가 이때까지 방문한 거리의 최소보다 작다면 그 위치로 다시 먹을 수 있는 후보 sub 벡터에 푸시한다. 거리가 같으면 여러 물고기를 담을 수 있어서 이렇게 한다

거리가 같다면 그냥 벡터에 푸시한다

반복문이 끝나고 sub 벡터가 비어있으면 먹을게 없다는 소리이고 안 비어있다면 문제에서 주어진 조건 중 위에 있으며 왼쪽에 있는 물고기가 우선이라는 조건을 따라 정렬해준다

그렇게 물고기를 찾아 리턴한다

물고기를 찾았으면 그 물고기까지의 거리를 답에 더해주고 먹은 횟수를 증가시키고 크기를 증가시킬지 말지 결정한다

그리고 상어의 위치를 업데이트하고 배열도 업데이트 해준다. 그렇게 나머지 로직을 반복하면서 더 이상 먹을 수 있는 물고기가 없을 때까지를 구한다

코드

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[24][24];

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

struct Pos
{
    int y, x;
};

int shark = 2;
int eat_count = 0;
Pos sharkPos;

void Input()
{
    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)
            {
                sharkPos = { i, j };
                arr[i][j] = 0;
            }
        }
    }
}

void BFS()
{
    memset(visited, -1, sizeof(visited));

    queue<Pos> q;
    q.push(sharkPos);
    visited[sharkPos.y][sharkPos.x] = 0;

    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

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

            if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] != -1) continue;
            if (shark < arr[ny][nx]) continue;

            visited[ny][nx] = visited[y][x] + 1;
            q.push({ ny, nx });
        }
    }
}


bool CanEat(Pos pos)
{
    if (shark > arr[pos.y][pos.x])
        return true;
    else
        return false;
}

bool Compare(Pos& p1, Pos& p2)
{
    if (p1.y == p2.y)
    {
        return p1.x < p2.x;
    }

    return p1.y < p2.y;
}

Pos FindFish()
{
    Pos ret = { -1, -1 };

    int distance = 1000000;

    vector<Pos> sub;

    BFS();

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // 물고기이며 상어보다 크기가 작은 물고기를 찾는다 -> 먹을 수 있는 물고기를 찾는다와 같은 의미
            if (arr[i][j] >= 1 && arr[i][j] < shark && visited[i][j] != -1)
            {
                if (visited[i][j] < distance)
                {
                    distance = visited[i][j];
                    sub.clear();
                    sub.push_back({ i, j });
                }
                else if (visited[i][j] == distance)
                {
                    sub.push_back({ i, j });
                }
            }
        }
    }

    if (!sub.empty())
    {
        sort(sub.begin(), sub.end(), Compare);
        ret = sub[0];
    }

    return ret;
}

void Solve()
{
    int answer = 0;

    while (true)
    {
        Pos pos = FindFish();

        if (pos.y == -1 && pos.x == -1) break;

        answer += (visited[pos.y][pos.x]);
        sharkPos = pos;
        arr[pos.y][pos.x] = 0;
        eat_count++;

        if (shark == eat_count)
        {
            shark++;
            eat_count = 0;
        }
    }

    cout << answer;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Input();

    Solve();

    return 0;
}

회고

이런 복잡한 문제는 구현만 잘하면 어렵진 않은데 문제 이해력이 정말 중요한 것 같다

서두르지 말고 조건 하나하나를 따져 로직을 분리해보자