문제 접근

시간제한이 2초였고 메모리도 512로 매우 널널했다. N의 크기도 최대 20이였기에 칸은 고작해야 400칸이다. 현재 위치에서 매번 BFS를 돌려서, 이동 경로가 가장 가까운 먹을 수 있는 물고기가 있는 곳으로 펭귄을 이동시키면 된다. 하지만, 여기서 처음에 예제4번이 계속 60이 아니라 56이 나와서 헤맸는데, 이유는 다음과 같았다. 처음 구현했을때, 이동경로거리가 같은 경우 더 위쪽에 있는 걸로, 그리고 더 왼쪽에 있는 물고기를 먼저 먹어야 한다고 해서 BFS탐색시 위,왼쪽,오른,아래 로 탐색을 하고 먹을 수 있는 물고기가 나오면 bfs를 종료했다.
1시간 헤매다가 질문게시판을 보니, 나와 비슷하게 생각하는 사람들이 매우 많았다. 알고보니 바로 끝내면 안되고 모든 최단거리의 물고기들을 대상으로 x와 y좌표에 대해 정렬을 시켜야하는 문제였다.
아래와 같은 경우가 있다고 하자. 9는 현재 펭귄 위치고, 이때 펭귄의 좌표는 (0,2)이고 사이즈는 4다. 따라서, 3이하의 물고기들을 먹을 수 있다.
이 경우 내가 처음 생각한대로 bfs를 하고 조기에 종료시키면 (1,1)에 위치한 3사이즈의 물고기를 먹으러 가야 한다 하지만, (0,4)가 이 문제에서 원한 다음 먹어야 하는 물고기다. 둘이 이동 거리는 2로 같으나 (0,4)가 더 위에 있기 때문이다.

5 4 9 0 3 4
4 3 0 3 4 5
3 2 0 5 6 6
2 0 0 3 4 5
3 2 0 6 5 4
6 6 6 6 6 6

문제 풀이

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

class Main {
    static int N;
    static int[][] graph;
    static Penguin penguin;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 9) {
                    penguin = new Penguin(i, j);
                    graph[i][j] = 0;
                }
            }
        }

        while (true) {
            int turnMoveSize = penguin.moveNext();
            if (turnMoveSize == 0) break;
            answer += turnMoveSize;
        }

        System.out.println(answer);
    }

    static class Penguin {
        int x;
        int y;
        int eatCount;
        int size;

        Penguin(int x, int y) {
            this.x = x;
            this.y = y;
            size = 2;
            eatCount = 0;
        }

        void eat(int nextX, int nextY) {
            eatCount++;
            if (eatCount == size) {
                size++;
                eatCount = 0;
            }
            this.x = nextX;
            this.y = nextY;
            Main.graph[x][y] = 0;
        }

        static int[] dx = {-1, 0, 0, 1};
        static int[] dy = {0, -1, 1, 0};

        int moveNext() {
            LinkedList<Node> q = new LinkedList<>();
            boolean[][] isVisited = new boolean[Main.N][Main.N];
            isVisited[x][y] = true;
            q.add(new Node(x, y, 0));

            boolean isFind = false;
            int result = 0;
            ArrayList<Node> nodes = new ArrayList<>();

            while (!q.isEmpty()) {
                Node curN = q.poll();
                if (isFind && curN.d >= result) break; // 조기에 BFS 종료시키기 위해
                for (int i = 0; i < 4; i++) {
                    int nextX = curN.x + dx[i];
                    int nextY = curN.y + dy[i];
                    if (isIn(nextX, nextY) && !isVisited[nextX][nextY]) {
                        isVisited[nextX][nextY] = true;
                        if (Main.graph[nextX][nextY] == 0) {
                            q.add(new Node(nextX, nextY, curN.d + 1));
                            continue;
                        }

                        if (Main.graph[nextX][nextY] < this.size) {
                            if (isFind) {
                                if (result == curN.d + 1) {
                                    nodes.add(new Node(nextX, nextY, curN.d + 1));
                                }
                            } else {
                                isFind = true;
                                result = curN.d + 1;
                                nodes.add(new Node(nextX, nextY, curN.d + 1));
                            }
                        } else if (Main.graph[nextX][nextY] == this.size) {
                            q.add(new Node(nextX, nextY, curN.d + 1));
                        }
                    }
                }
            }

            if (isFind) {
                nodes.sort((n1, n2) -> {
                    if (n1.x == n2.x) {
                        return n1.y - n2.y;
                    } else {
                        return n1.x - n2.x;
                    }
                });
                Node next = nodes.get(0);
                eat(next.x, next.y);
            }

            return result;
        }

        private boolean isIn(int x, int y) {
            return x >= 0 && x < Main.N && y >= 0 && y < Main.N;
        }
    }

    static class Node {
        int x;
        int y;
        int d;

        Node(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}

초기에 풀었던 로직에는 BFS부분에 isFind와 result를 검사하지 않았다. 때문에 시간이 아주 좀 더 걸렸다.

bfs의 특징을 생각해보면 위 코드와 같이 조건을 추가해서 조기에 종료시킬 수 있다.
(코드양이 감소한 이유는 리팩토링을 조금 해줘서 그렇다. 성능상 미치는 영향은 없었다)