[백준 / 골드3] 16236 아기 상어 (Java)

문제 보기

사용한 것

• 현재 거리에서 가장 가까운(거리 같으면 위, 왼쪽 우선) 먹을 수 있는 물고기를 찾기 위한 BFS, 우선순위 큐

풀이 방법

• 현재 위치에서 먹을 수 있는 물고기가 없을 때까지 BFS
• 다음 좌표를 우선순위 큐를 활용해 위쪽, 왼쪽을 우선으로 탐색
• 물고기를 특정 개수 먹으면 아기 상어 크기 증가

코드

public class Main {

    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};
    private static int n;
    private static int[][] map;
    private static int x;
    private static int y;
    private static int size;
    private static int ct;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findMaxTime());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        size = 2;
        ct = 0;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int size = Integer.parseInt(st.nextToken());
                if (size == 9) {
                    x = i;
                    y = j;
                    map[i][j] = 0;
                } else {
                    map[i][j] = size;
                }
            }
        }
        br.close();
    }

    private static int findMaxTime() {
        int time = 0;
        while (true) {
            int move = eat();
            if (move == 0) {
                break;
            }
            if (++ct == size) {
                size++;
                ct = 0;
            }
            time += move;
        }
        return time;
    }

    private static int eat() {
        int move = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> {
            if (o1[2] == o2[2]) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
            return o1[2] - o2[2];
        });
        q.offer(new int[]{x, y, 0});
        boolean[][] visited = new boolean[n][n];
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cm = cur[2];
            int cs = map[cx][cy];

            if (cs > 0 && cs < size) {
                map[cx][cy] = 0;
                move = cm;
                x = cx;
                y = cy;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + DX[i];
                int ny = cy + DY[i];

                if (isOOB(nx, ny) || visited[nx][ny] || map[nx][ny] > size) {
                    continue;
                }

                q.offer(new int[]{nx, ny, cm + 1});
                visited[nx][ny] = true;
            }
        }
        return move;
    }

    private static boolean isOOB(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= n;
    }
}