[BOJ] 17086 아기상어2

아기상어2

풀이

• 어떤 칸의 안전거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리
• 이동은 8방향이 가능하다.
• 안전거리가 가장 큰 칸을 구하라
• map에서 0인 각 칸에 대해서 최초로 1을 만날 때 까지 bfs를 수행하며 이동 거리를 저장한다.
• 그 중 가장 큰 거리를 정답으로 출력한다.
• 계속 메모리 초과가 나서 왜지 했는데 bfs 내부에서 방문처리를 안했었다...🥹

코드

import java.util.*;
import java.io.*;
public class Main {
    static int answer = Integer.MIN_VALUE;
    static int[][] map;
    static boolean[][] visited;
    static int N,M;
    static  int t_cnt;
    static int[] dx = {-1,1,0,0,-1,-1,1,1};
    static int[] dy = {0,0,-1,1,-1,1,-1,1};
    public static void main(String[] args) throws Exception{
        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++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==0){
                    t_cnt = Integer.MAX_VALUE;
                    visited = new boolean[N][M];
                    bfs(i,j);
                    answer = Math.max(answer,t_cnt);
                }
            }
        }
        System.out.println(answer);
    }
    private static void bfs(int i,int j){
        visited[i][j] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i,j,0});

        L:while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            int cnt = cur[2];
            for(int d=0;d<8;d++){
                    int nx = x+dx[d];
                    int ny = y+dy[d];
                    if(nx>=0 && nx<N && ny>=0 && ny<M && !visited[nx][ny]){
                        if(map[nx][ny]==0){
                            visited[nx][ny]=true;
                            queue.add(new int[]{nx,ny,cnt+1});
                        }
                        else {
                            t_cnt = Math.min(t_cnt,cnt+1);
                            break L;
                        }
                    }
            }
        }
    }
}