백준 아기 상어

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다.
공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

내가 이 문제를 보고 생각해본 부분

입력 및 초기화
N×N 크기 공간 배열을 입력받는다.
아기 상어 위치를 찾아 sharkPos에 저장하고, 해당 칸은 빈칸(0)으로 바꾼다.
아기 상어 크기는 2, 먹은 횟수는 0, 시간은 0으로 초기화한다.
시뮬레이션 반복
bfs 함수로 먹을 수 있는 최단 거리 물고기를 찾는다.
더 이상 먹을 물고기가 없으면 bfs가 null을 반환하고, 루프 종료한다.
먹을 물고기가 있으면 거리(시간)를 누적하고, 상어 위치를 변경하며 물고기를 먹어 빈칸으로 만든다.
먹은 물고기 수가 현재 상어 크기와 같으면 상어 크기를 1 증가시키고 먹은 물고기 수를 초기화한다.
bfs 함수
상어 현재 위치에서부터 너비 우선 탐색을 하면서 이동할 수 있는 칸을 탐색한다.
상어 크기보다 큰 물고기가 있으면 그 칸으로는 이동하지 않는다.
먹을 수 있는 물고기(상어 크기보다 작은 물고기)를 발견하면 그 최단 거리 저장하고 이후 같은 거리까지 후보 수집한다.
거리 기준 후보가 여러 개 있으면 가장 위쪽, 그다음 가장 왼쪽 순으로 정렬해 첫 번째 물고기 반환한다.
결과 출력
아기 상어가 엄마 상어의 도움 없이 먹을 수 있었던 총 시간을 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 백준 16236번 문제
public class Main1318 {
    static int N;
    static int[][] map;
    static int sharkSize = 2;
    static int eaten = 0; // 먹은 물고기 수
    static int time = 0; // 총 소요 시간
    static int[] sharkPos = new int[2];

    // 상하좌우 이동
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0 ; i < N ; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(input[j]);
                if (map[i][j] == 9) {
                    sharkPos[0] = i;
                    sharkPos[1] = j;
                    map[i][j] = 0; // 아기 상어 위치는 빈 칸으로 변경
                }
            }
        }

        // 먹을 물고기가 없을 때까지 시뮬레이션 반복
        while (true) {
            int[] target = bfs(sharkPos[0], sharkPos[1]);
            if (target == null) break; // 먹을 물고기 없음 -> 종료
            time += target[2]; // 이동 시간 누적
            sharkPos[0] = target[0];
            sharkPos[1] = target[1];
            map[target[0]][target[1]] = 0; // 물고기 먹음
            eaten++;
            if (eaten == sharkSize) {
                sharkSize++;
                eaten = 0;
            }
        }

        System.out.println(time);
        br.close();
    }

    // 가장 가까운 먹을 수 있는 물고기 찾아 BFS 탐색
    static int[] bfs(int x, int y) {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y, 0}); // 좌표와 거리
        visited[x][y] = true;

        List<int[]> candidates = new ArrayList<>();
        int minDist = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            int dist = cur[2];

            if (dist > minDist) break; // 더 먼 거리 물고기는 탐색할 필요 없음

            // 먹을 수 있는 물고기 발견 (크기 작음)
            if (map[cx][cy] > 0 && map[cx][cy] < sharkSize) {
                candidates.add(new int[]{cx, cy, dist});
                minDist = dist; // 최단 거리 갱신
            }

            // 이동 가능한 칸 탐색
            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 && !visited[nx][ny]) {
                    // 자신의 크기보다 크면 지나갈 수 없음
                    if (map[nx][ny] <= sharkSize) {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny, dist + 1});
                    }
                }
            }
        }

        if (candidates.isEmpty()) return null;

        // 우선순위: 가장 위 -> 가장 왼쪽
        candidates.sort((a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        return candidates.get(0);
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.