문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  = 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  = 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
  = 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치
• 아기 상어는 공간에 한 마리 있다.

출력

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

예제1 - 입력

3
0 0 0
0 0 0
0 9 0

예제1 - 출력

0

예제2 - 입력

3
0 0 1
0 0 0
0 9 0

예제2 - 출력

3

예제3 - 입력

4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

예제3 - 출력

14

예제4 - 입력

6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

예제4 - 출력

60

예제5 - 입력

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

예제5 - 출력

48

예제6 - 입력

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

예제6 - 출력

39

제출 코드

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

public class Main {
    static Pair shark;
    static int[] mx = {-1, 1, 0, 0};
    static int[] my = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] sea = new int[n][n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                sea[i][j] = Integer.parseInt(st.nextToken());
                if (sea[i][j] == 9) {
                    sea[i][j] = 0;
                    shark = new Pair(i, j, 0);
                }
            }
        }
        br.close();
        
        int time = 0;
        int eat = 0;
        int size = 2;
        while (true) {
            PriorityQueue<Pair> fishes = new PriorityQueue<>(new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    if (o1.dist == o2.dist) {
                        if (o1.x != o2.x)
                            return Integer.compare(o1.x, o2.x);
                        return Integer.compare(o1.y, o2.y);
                    }
                    return Integer.compare(o1.dist, o2.dist);
                }
            });

            boolean[][] visited = new boolean[n][n];

            fishes.offer(new Pair(shark.x, shark.y, 0));
            visited[shark.x][shark.y] = true;

            boolean check = false;
            while (!fishes.isEmpty()) {
                shark = fishes.poll();

                if (sea[shark.x][shark.y] != 0 && sea[shark.x][shark.y] < size) {
                    sea[shark.x][shark.y] = 0;
                    eat++;
                    time+= shark.dist;
                    check = true;
                    break;
                }

                for (int i = 0; i < mx.length; i++) {
                    int tx = shark.x + mx[i];
                    int ty = shark.y + my[i];
                    int dist = shark.dist;

                    if (tx < 0 || tx >= n || ty < 0 || ty >= n)
                        continue;

                    if (!visited[tx][ty] && sea[tx][ty] <= size){
                        fishes.offer(new Pair(tx, ty, dist + 1));
                        visited[tx][ty] = true;
                    }
                }
            }
            if (!check)
                break;
            if (size == eat) {
                size++;
                eat = 0;
            }
        }
        System.out.println(time);
    }
    static class Pair {
        public int x;
        public int y;
        public int dist;
        public Pair(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}