BOJ 17086 아기 상어 2

https://www.acmicpc.net/problem/17086

문제

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

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

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

---

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

---

출력

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

---

예제 입력 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

---

코드

N, M이 충분히 작아 BFS나 브루트포스로도 풀 수 있는 문제였다.
방향이 8개나 있어서 방향 벡터를 의미하는 배열을 초기화하기 귀찮기 때문에 브루트포스로 해결했다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static int[][] map;
    static List<Point> sharks = new ArrayList<>();

    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                String input = st.nextToken();

                if(input.equals("1")) {
                    map[i][j] = 1;
                    sharks.add(new Point(i, j));
                }
            }
        }

        int answer = calculateMaxSafeDistance();

        System.out.println(answer);
    }

    static int calculateMaxSafeDistance() {
        int maxSafeDistance = 0;

        // 빈 칸만 골라 해당 칸의 안전 거리를 계산해서 그 중 최대값을 구한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 0) {
                    int safeDistance = calculateSafeDistance(i, j);
                    maxSafeDistance = Math.max(maxSafeDistance, safeDistance);
                }
            }
        }

        return maxSafeDistance;
    }

    static int calculateSafeDistance(int r, int c) {
        // 빈 칸과 상어 수가 각각 한 개 이상이라는 조건이 있기 때문에,
        // 마지막에 구한 안전 거리가 MAX_VALUE가 아니라는 보장이 가능하다.
        int safeDistance = Integer.MAX_VALUE;

        for (Point shark: sharks) {
            int diffX = Math.abs(r - shark.x);
            int diffY = Math.abs(c - shark.y);
            int distance = Math.max(diffX, diffY);
            safeDistance = Math.min(safeDistance, distance);
        }

        return safeDistance;
    }
}