[백준] 17086. 아기 상어 2

문제 링크

[백준] 17086. 아기 상어 2

풀이 과정

안전 거리 는 빈 칸과 가장 거리가 가까운 상어까지의 거리입니다. 모든 빈 칸으로부터의 안전 거리를 구해봐야, 비로소 그 값이 최대값임을 알 수 있습니다. 따라서, 모든 빈 칸 좌표로부터 BFS 탐색을 수행해야합니다.

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visit;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}, dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static int answer;

    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];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    bfs(i, j);
                }
            }
        }

        System.out.println(answer);
    }

    static void bfs(int x, int y) {
        for (boolean[] arr : visit) Arrays.fill(arr, false);

        Queue<int[]> q = new LinkedList<>();
        visit[x][y] = true;
        q.add(new int[]{x, y});
        int cnt = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                int[] now = q.poll();

                if (map[now[0]][now[1]] == 1) {
                    answer = Math.max(answer, cnt);

                    return;
                }

                for (int d = 0; d < 8; d++) {
                    int nx = now[0] + dx[d], ny = now[1] + dy[d];

                    if (!isRange(nx, ny) || visit[nx][ny]) continue;

                    visit[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }

            cnt++;
        }
    }

    static boolean isRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}