문제

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

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

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

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제1 - 입력

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제1 - 출력

2

예제2 - 입력

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제2 - 출력

2

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] sea = new int[n][m];
        LinkedList<Pair> sharks = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                sea[i][j] = Integer.parseInt(st.nextToken());
                if (sea[i][j] == 1) {
                    sharks.add(new Pair(i, j));
                }
            }
        }

        int[] mx = {0, 0, -1, 1, 1, 1, -1, -1};
        int[] my = {-1, 1, 0, 0, 1, -1, 1, -1};
        int[][][] visited = new int[sharks.size()][n][m];

        int cur = 0;
        int answer = 0;
        for (Pair s : sharks) {
            Queue<Pair> queue = new LinkedList<>();
            queue.offer(s);
            visited[cur][s.x][s.y] = 1;
            while (!queue.isEmpty()) {
                Pair now = queue.poll();

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

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

                    if (visited[cur][tx][ty] == 0) {
                        queue.offer(new Pair(tx, ty, dist + 1));
                        visited[cur][tx][ty] = dist + 1;
                    }
                }
            }
            cur++;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int temp = n * m;
                for (int s = 0; s < sharks.size(); s++) {
                    if (temp > visited[s][i][j] - 1)
                        temp = visited[s][i][j] - 1;
                }
                if (temp > answer)
                    answer = temp;
            }
        }
        System.out.println(answer);
    }
    static class Pair {
        public int x;
        public int y;
        public int dist = 0;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public Pair(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}