백준 - 아기상어 (java)

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

public class Main {
    static class Shark {
        int x, y, size, eatCount;
        
        Shark(int x, int y) {
            this.x = x;
            this.y = y;
            this.size = 2;
            this.eatCount = 0;
        }
    }
    
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static Shark shark;
    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    shark = new Shark(i, j);
                    map[i][j] = 0; // 상어의 시작 위치는 빈 칸으로 변경
                }
            }
        }
        
        System.out.println(bfs());
    }
    
    static int bfs() {
        int time = 0;
        
        while (true) {
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[2] == o2[2]) {
                        if (o1[0] == o2[0]) {
                            return Integer.compare(o1[1], o2[1]);
                        }
                        return Integer.compare(o1[0], o2[0]);
                    }
                    return Integer.compare(o1[2], o2[2]);
                }
            });
            
            visited = new boolean[N][N];
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{shark.x, shark.y, 0});
            visited[shark.x][shark.y] = true;
            
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int cx = cur[0], cy = cur[1], dist = cur[2];
                
                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] <= shark.size) {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny, dist + 1});
                            if (map[nx][ny] > 0 && map[nx][ny] < shark.size) {
                                pq.add(new int[]{nx, ny, dist + 1});
                            }
                        }
                    }
                }
            }
            
            if (pq.isEmpty()) {
                return time;
            }
            
            int[] fish = pq.poll();
            shark.x = fish[0];
            shark.y = fish[1];
            time += fish[2];
            shark.eatCount++;
            map[shark.x][shark.y] = 0;
            
            if (shark.eatCount == shark.size) {
                shark.size++;
                shark.eatCount = 0;
            }
        }
    }
}

정렬기준을 priorityqueue로 구현한다. priorityqueue에는 물고기만 넣어주고 탐색을 진행할 queue를 따로 넣어준다. 모든 탐색을 마치면 priorityqueue의 물고기를 처리해주고 물고기 먹는 숫자도 세서 사이즈와 같으면 size++, 카운트를 0으로 초기화 해준다.