BOJ_17086 아기상어 2 [Java] (S2)

문제 설명

풀이

일단 상어마다 모두 주변을 확인해서, 안전거리를 모두 구해야한다. 그렇게 생각하면 어떻게 모두 확인해볼지 생각해봐야 한다.

 

계속해서 안전거리를 추가해줘야하니 DFS나 BFS를 해줘야하는데, 끝까지 갈필요 없이, 최대한 인접한 곳을 보는 것이니 BFS로 하였다.

 

그리고 매우 기초적인 BFS라서 BFS의 흐름을 풀어보기에 좋은 문제였다.

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = 0;
        map = new int[N+1][M+1];
        dis = new int[N+1][M+1];

        Queue<int[]> que = new LinkedList<int[]>();

        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());
                if(map[i][j] == 1){
                    que.add(new int[] {i,j});
                }
            }
        }

        while (!que.isEmpty()) {
            int[] now =  que.poll();
            int x = now[0];
            int y = now[1];

            for(int z=0; z<8; z++){
                int cx = x + dx[z];
                int cy = y + dy[z];

                if(cx < 0 || cy < 0 || cx >= M || cy >= N || map[cx][cy] == 1 || dis[cx][cy] != 0){
                    continue;
                }

                dis[cx][cy] = dis[x][y] + 1;
                if (dis[cx][cy] > count){
                    count = dis[cx][cy];
                }
                que.add(new int[] {cx,cy});
            }
        }

        System.out.println(count);

    }
}

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

17086번: 아기 상어 2