[백준 17086] 아기 상어 2

생각 정리

• 아기 상어끼리의 안전거리 최댓값을 구한다고 생각했음

• 그래서 아기상어에서 다른 아기상어까지의 거리 중 최댓값을 구함

• But, 문제는 아기상어끼리의 최댓값이 아니고 특정 칸에서 아기 상어들과의 안전거리의 최댓값을 구하는 것이었음 => 즉, 상어가 있는 칸에서 bfs를 하는 것이 아님

• 상어가 없는 칸에서 안전거리를 구하고, 상어가 없는 모든 칸에서 안전거리를 다 구한 다음 안전거리의 최대값을 구한다.

  1. 0이고 아직 방문을 하지 않았을 떄, 안전거리를 구한다. (bfs 탐색)
  2. bfs탐색을 하다가 1을 만나면(=상어를 만나면) 그 때의 안전거리로 안전거리의 최대값을 업데이트 한다.
  3. bfs가 끝나면 방문여부를 다시 초기화 한다.

코드

import java.util.*;
import java.io.*;

class Position{
    int x;
    int y;
    
    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main {
    static int N, M, max = 0;
    static int[][] space, dist;
    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());

        space = new int[N][M];
        dist = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dist[i], -1);
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(space[i][j] == 0 && dist[i][j] == -1){
                    bfs(i, j);

                    for(int k=0; k<N; k++)
                        Arrays.fill(dist[k], -1); //다시 업뎃
                }
            }

        }


        System.out.println(max);

    }

    static void bfs(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
        int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};

        queue.add(new Position(x, y));
        dist[x][y] = 0;

        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<8; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny < 0 || nx >=N || ny >= M) continue;
                if(dist[nx][ny] >= 0) continue;
                queue.add(new Position(nx, ny));
                dist[nx][ny] = dist[out.x][out.y] + 1;
                
                if(space[nx][ny] == 1) { // 다른 아기 상어를 만났을 경우 
                    max = Math.max(max, dist[nx][ny]);
                    return ;
                }
            }
        }
    }
    
}