아이디어

• 구현 문제
• 타겟을 찾는 건 BFS로 구현하자.
  • 규칙을 적용하기 위해 PriorityQueue를 적용했다.
  • BFS 데이터에 depth를 넣어 PQ 비교함수에 적용하거나, depth를 세기 위한 Queue와 PQ를 동시에 사용하는 방법
  • 필자는 후자를 사용했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

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

    static Queue<Node> q = new ArrayDeque<>();
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static boolean[][] enqueued;

    static int N, ans;
    static Fish[][] map;
    static Shark shark;


    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(rd.readLine());

        map = new Fish[N][N];
        for (int y=0; y<N; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<N; x++) {
                int n = Integer.parseInt(tk.nextToken());
                if (n == 9)
                    shark = new Shark(y, x);
                else if (n > 0)
                    map[y][x] = new Fish(y, x, n);
            }
        }

        while (true) {
            FindResult result = findTarget();
            if (result == null)
                break;

            eat(result.target);
            ans += result.dist;
        }

        System.out.println(ans);
    }

    static class Fish {
        int y, x;
        int size;

        Fish(int y, int x, int size) {
            this.y = y;
            this.x = x;
            this.size = size;
        }
    }

    static class Shark extends Fish {
        int eaten;

        Shark(int y, int x) {
            super(y, x, 2);
            this.eaten = 0;
        }

        boolean isEdible(Fish f) {
            return f.size < this.size;
        }

        boolean isPassable(Fish f) {
            return f == null || f.size <= this.size;
        }
    }

    static class Node implements Comparable<Node> {
        int y, x;
        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public int compareTo(Node o) {
            int c1 = Integer.compare(this.y, o.y);
            if (c1 != 0) return c1;
            return Integer.compare(this.x, o.x);

        }
    }

    static class FindResult {
        Fish target;
        int dist;
        FindResult(Fish target, int dist) {
            this.target = target;
            this.dist = dist;
        }
    }

    static FindResult findTarget() {
        q.clear();
        pq.clear();
        enqueued = new boolean[N][N];

        q.offer(new Node(shark.y, shark.x));
        enqueued[shark.y][shark.x] = true;

        int dist = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                Node node = q.poll();
                int y = node.y;
                int x = node.x;

                Fish f = map[y][x];
                if (f != null && shark.isEdible(f))
                    return new FindResult(f, dist);

                for (int d=0; d<4; d++) {
                    int ny = y + dy[d];
                    int nx = x + dx[d];
                    if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                    if (enqueued[ny][nx]) continue;
                    Fish nf = map[ny][nx];
                    if (!shark.isPassable(nf)) continue;

                    pq.offer(new Node(ny, nx));
                    enqueued[ny][nx] = true;
                }
            }
            while (!pq.isEmpty()) {
                q.offer(pq.poll());
            }
            dist++;
        }
        return null;
    }

    static void eat(Fish f) {
        shark.y = f.y;
        shark.x = f.x;
        map[f.y][f.x] = null;

        shark.eaten++;
        if (shark.eaten >= shark.size) {
            shark.size++;
            shark.eaten = 0;
        }
    }
}

메모리 및 시간

• 메모리: 14684 KB
• 시간: 144 ms

리뷰

• PQ와 Queue를 동시에 사용하는 경우를 알아보았다.