[백준] 아기 상어 (시뮬레이션)

문제 소개

아기 상어 - 백준 16236번 문제를 정리합니다.
이 문제는 시뮬레이션과 BFS를 통해 아기 상어가 먹을 수 있는 물고기를 탐색하며 최단 경로로 이동하는 구현 문제입니다.

핵심은 먹을 수 있는 물고기 중 가장 가까운 위치를 판단하고, 아기 상어의 성장 조건을 반영해 상태를 계속 갱신하는 점입니다.

문제 링크: 아기 상어 - 백준 16236번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 시작 위치에서 BFS 탐색하여 먹을 수 있는 물고기를 찾음
2. 거리 우선 + 위 → 왼쪽 우선 정렬 조건으로 가장 적절한 물고기 선택
3. 먹은 후 아기 상어의 위치 갱신 및 크기 증가 조건 체크
4. 더 이상 먹을 수 없을 때 종료

---

해결 과정 및 코드

핵심 아이디어

1. 아기 상어는 크기 이하의 칸은 이동 가능, 작은 물고기만 먹을 수 있음
2. BFS를 통해 한 턴씩 탐색하며, 같은 거리의 물고기 중 위쪽, 왼쪽 우선 순위로 선택
3. 먹을 때마다 먹은 횟수 카운팅, 아기 상어 크기만큼 먹으면 크기 증가
4. 더 이상 먹을 수 있는 물고기가 없다면 while 루프 종료

코드

시간 복잡도 :O(N^2 * N^2)
이유: 한 번의 BFS에 O(N²), 전체 과정에서 최대 O(N²)번 BFS 수행 가능 (물고기 수가 N²이기 때문)

 

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] board;
    static int [][] delta = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; // 상좌우하
    static int [] shark = new int [2]; // y, x 위치

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = read();
        board = new int[N][N];
        int fishCnt = 0;

        // 입력 처리
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = read();
                if (board[i][j] > 0 && board[i][j] < 9) fishCnt++; // 물고기 수 카운트
                else if (board[i][j] == 9) {
                    shark[0] = i; shark[1] = j; // 아기 상어 초기 위치 저장
                    board[i][j] = 0; // 위치 초기화
                }
            }
        }

        // 총 시간 출력
        bw.write(Integer.toString(calculateTime(fishCnt)));
        bw.flush();
    }

    private static int calculateTime(int fishCount) {
        int sharkSize = 2, totalTime = 0, eatenFish = 0;

        while (fishCount > 0) {
            int distance = findClosestFish(sharkSize);
            if (distance == 0) break; // 먹을 물고기 없음 → 종료

            totalTime += distance;
            fishCount--;
            eatenFish++;

            // 크기 증가 조건
            if (eatenFish == sharkSize) {
                sharkSize++;
                eatenFish = 0;
            }
        }
        return totalTime;
    }

    private static int findClosestFish(int sharkSize) {
        boolean[][] visited = new boolean[N][N];
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] { shark[0], shark[1] });
        visited[shark[0]][shark[1]] = true;

        int distance = 0;
        int targetY = -1, targetX = -1;

        while (!queue.isEmpty()) {
            boolean isEatFish = false;

            for (int size = queue.size(); size > 0; size--) {
                int[] cur = queue.poll();

                for (int d = 0; d < 4; d++) {
                    int ny = cur[0] + delta[d][0], nx = cur[1] + delta[d][1];
                    if (isOut(ny, nx) || visited[ny][nx] || board[ny][nx] > sharkSize) continue;
                    queue.add(new int[] { ny, nx });
                    visited[ny][nx] = true;

                    // 먹을 수 있는 물고기 찾기
                    if (board[ny][nx] > 0 && board[ny][nx] < sharkSize) {
                        isEatFish = true;
                        if (targetY == -1 || ny < targetY || (ny == targetY && nx < targetX)) {
                            targetY = ny;
                            targetX = nx;
                        }
                    }
                }
            }

            distance++;
            if (isEatFish) {
                // 해당 물고기 먹기
                board[targetY][targetX] = 0;
                shark[0] = targetY; shark[1] = targetX;
                return distance;
            }
        }
        return 0;
    }

    static boolean isOut(int ny, int nx){
        return ny < 0 || nx < 0 || nx >= N || ny >= N;
    }

    static int read() throws Exception{
        int n = System.in.read() & 15, cur;
        while ((cur = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (cur & 15);
        }
        return n;
    }
}