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

문제

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

16236번: 아기 상어

---

문제 요약

N × N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.

 

공간은 1 × 1 크기의 정사각형 칸으로 나누어져 있고, 한 칸에는 물고기가 최대 1마리 존재한다.

 

아기 상어와 물고기는 모두 크기를 갖고 있고, 초기 아기 상어의 크기는 2이다.

 

아기 상어는 1초에 상하좌우로 인접한 1칸씩 이동할 수 있다.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나 갈 수 없고, 자신보다 작은 물고기만 먹으면서 이동할 수 있다. (크기가 같은 물고기는 먹을 수 없지만, 그 칸을 지나갈 수 있다.)

 

아기 상어가 어느 칸으로 이동할 지 결정하는 방법은 아래와 같다.

1. 먹을 수 있는 물고기가 없다면, 엄마 상어에게 도움을 요청한다.

2. 먹을 수 있는 물고기가 1마리 이상이라면, 거리가 가장 가까운 물고기를 먹으러간다.

2 - 1. 거리가 가장 가까운 물고기가 많다면, 가장 위에 있는 물고기를 먹는다.

2 - 2. 가장 위에 있는 물고기가 많다면, 가장 왼쪽에 있는 물고기를 먹는다.

 

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다.

즉, 이동과 동식에 물고기를 먹고, 그 칸은 빈 칸이 된다.

 

아기 상어가 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.

 

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 출력한다.

+ 빈 칸은 0, 아기 상어의 위치는 9, 나머지 숫자는 그 칸에 있는 물고기의 크기이다.

---

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <cstring>

#define MAX_N 20

using namespace std;

int arr[MAX_N + 1][MAX_N + 1];
bool visited[MAX_N + 1][MAX_N + 1];

int n;

// 우선 순위가 위쪽, 왼쪽이므로 순서 주의
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

int shark_size = 2;
int shark_x, shark_y;
int size_up;

int res;

bool stop, eat;

// 한 마리를 먹을 때까지 이동
void bfs(int start_x, int start_y, bool visited[][MAX_N + 1]) {
    queue<tuple<int, int, int>> q;
    q.push({ start_x, start_y, 0 });
    visited[start_x][start_y] = true;

    int tmp_tm; // 한 마리를 먹는 데 걸린 시간

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

        // 이전 값과 비교해서 더 위쪽 - 왼쪽에 있는 곳에 있는 물고기를 먹으러 이동
        if (arr[x][y] > 0 && arr[x][y] < shark_size && tmp_tm == tm) {
            if ((shark_x > x) || (shark_x == x && shark_y > y)) {
                shark_x = x;
                shark_y = y;
                continue;
            }
        }

        // 이동한 위치에서 인접한 칸 탐색
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 방문했으면 패스
            if (visited[nx][ny]) continue;

            // 인덱스를 벗어나면 패스
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            // 갈 수 없으면 패스
            if (arr[nx][ny] > shark_size) continue;

            // 먹을 수 있는 물고기가 있으면
            if (arr[nx][ny] != 0 && arr[nx][ny] < shark_size && !eat) {
                // 먹음 체크
                eat = true;

                // 아기 상어 위치 변경
                shark_x = nx;
                shark_y = ny;

                // (nx, ny)에 있는 먹이를 먹는 데 걸리는 시간 임시 저장
                tmp_tm = tm + 1; 
                
                // 결과에 추가
                res += tmp_tm;
            }

            // 아무것도 없거나, 같은 크기의 물고기가 있다면
            else {
                q.push({ nx, ny, tm + 1 }); // 그냥 이동
                visited[nx][ny] = true;
            }
        }

    }
}

int main() {
    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) {
                shark_x = i;
                shark_y = j;
                arr[i][j] = 0;
            }
        }
    }

    while (!stop) {
        bool visited[MAX_N + 1][MAX_N + 1] = { false };

        bfs(shark_x, shark_y, visited); // 한 마리 먹을 때까지 이동

        // 먹을 것을 찾은 경우
        if (eat) {
            eat = false;
            size_up++;
            arr[shark_x][shark_y] = 0;

            // 상어 크기 증가
            if (size_up == shark_size) {
                shark_size++;
                size_up = 0;
            }
        }

        // 먹을 것을 못 찾은 경우
        else {
            stop = true;
        }
    }

    cout << res;

    return 0;
}

---

코드 설명

먹을 물고기가 더 이상 없을 때까지 하나씩 BFS 탐색을 통해 아기 상어가 먹을 물고기의 위치를 찾는다.

 

먹을 때마다 먹었던 물고기의 칸을 빈 칸으로 만들고,

만약, 아기 상어의 크기만큼 먹었다면 크기를 1 증가시키고, 다시 먹어야 하는 개수를 센다.

 

먹을 물고기를 찾지 못했다면, 탐색을 종료한다.

 

주의해야할 점은 우선 순위가 가까이 있는 물고기를 먼저 먹어야 한다는 점이다.

 

따라서 dx, dy 배열의 순서를 { 상, 좌, 우, 하 } 순으로 하고, 큐에 들어온 값 중 먹을 수 있는 물고기가 있으면  현재까지 발견한 물고기의 위치와 비교하여 더 위에, 더 왼쪽에 있는 물고기를 먹는다.