백준 16236번 [아기 상어](C++) -yes6686- 티스토리

백준 문제 풀이: 16236 [아기 상어]

---

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

문제 설명:

아기 상어가 NxN 크기의 공간에서 자신의 크기보다 작은 물고기를 먹으며 성장해나가는 문제입니다. 아기 상어는 상하좌우로 움직이며, 더 이상 먹을 수 있는 물고기가 없을 때까지 움직이는 시간을 계산해야 합니다.

입력:

• 첫 번째 줄에 공간의 크기 N이 주어집니다. (2 ≤ N ≤ 20)
• 다음 N개의 줄에는 공간의 상태가 주어집니다. 0은 빈 칸, 1~6은 물고기 크기, 9는 아기 상어의 위치입니다.

출력:

• 아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 걸린 시간을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

int arr[22][22];
int visited[22][22];
int dis[22][22];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n;

void bfs(int x, int y, int size, int eaten, int time) {
    queue<pair<int, int>> q;
    q.push({x, y});

    memset(visited, 0, sizeof(visited));
    memset(dis, 0, sizeof(dis));
    visited[x][y] = 1;

    int minDistance = 401;
    vector<pair<int, int>> targets;

    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
            if (visited[nx][ny] || arr[nx][ny] > size) continue;

            visited[nx][ny] = 1;
            dis[nx][ny] = dis[cx][cy] + 1;

            if (arr[nx][ny] != 0 && arr[nx][ny] < size) {
                if (dis[nx][ny] <= minDistance) {
                    if (dis[nx][ny] < minDistance) {
                        minDistance = dis[nx][ny];
                        targets.clear();
                    }
                    targets.push_back({nx, ny});
                }
            }

            q.push({nx, ny});
        }
    }

    if (targets.empty()) {
        cout << time << '\n';
        return;
    }

    sort(targets.begin(), targets.end());
    int tx = targets[0].first;
    int ty = targets[0].second;

    arr[x][y] = 0;
    arr[tx][ty] = 9;

    if (eaten + 1 == size) {
        bfs(tx, ty, size + 1, 0, time + minDistance);
    } else {
        bfs(tx, ty, size, eaten + 1, time + minDistance);
    }
}

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

    cin >> n;

    int sharkX = 1, sharkY = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                sharkX = i;
                sharkY = j;
            }
        }
    }

    bfs(sharkX, sharkY, 2, 0, 0);

    return 0;
}

예제

입력:
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

출력:
14

---

코드 설명

• 초기화: 상어의 위치를 찾고, BFS를 시작할 준비를 합니다.
• 탐색:
  • BFS를 사용하여 가장 가까운 물고기를 찾습니다.
  • 거리 기준으로 가장 가까운 물고기를 탐색하며, 동일 거리일 경우 우선순위를 고려해 정렬합니다.
• 먹기:
  • 가장 가까운 물고기를 먹고 상어의 크기를 업데이트합니다.
  • 남은 물고기가 없으면 현재까지의 시간을 출력합니다.

시간 복잡도

• 최대 BFS 탐색 범위는 N x N이며, 최대 물고기 개수가 400개이므로, 시간 복잡도는 O(N^2)입니다.

---

결과

코드는 주어진 문제를 정확히 해결하며, BFS를 활용해 가장 가까운 먹이를 효율적으로 탐색합니다. 상어의 이동 및 성장 로직이 올바르게 구현되었습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!