[BOJ] 17086 아기 상어 2 - JAVA

1. 문제

17086번: 아기 상어 2

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

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

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

---

2. 풀이

입력

board에 입력을 저장하고, 아기상어가 있는 위치를 큐에 넣는다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
 
Queue<int[]> queue = new ArrayDeque<>();
int[][] board = new int[N][M];
for(int i=0;i<N;i++){
   st = new StringTokenizer(in.readLine());
   for(int j=0;j<M;j++){
      board[i][j] = Integer.parseInt(st.nextToken());
      if(board[i][j]==1) queue.offer(new int[]{i,j});
   }
}

 

탐색

기본적인 BFS탐색이다. board[ni][nj]가 0이면 방문하고 새 값을 저장한다. 아기상어 주변으로 1 depth씩 탐색하므로 굳이 다익스트라처럼 저장된 값을 비교할 필요는 없다.

int max = 0;
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int[] now;
int ni,nj,val;
while(!queue.isEmpty()){
   now = queue.poll();
   val = board[now[0]][now[1]];
   max = Math.max(max,val);
 
   for(int[] d:deltas){
      ni = now[0]+d[0];
      nj = now[1]+d[1];
      if(ni<0||nj<0||ni>=N||nj>=M ||board[ni][nj]!=0) continue;
      board[ni][nj] = val+1;
      queue.offer(new int[]{ni,nj});
   }
}
 
System.out.println(max-1);

 

전체 코드

import java.io.*;
import java.util.*;
 
public class BOJ_17086_아기상어2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
 
      Queue<int[]> queue = new ArrayDeque<>();
      int[][] board = new int[N][M];
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<M;j++){
            board[i][j] = Integer.parseInt(st.nextToken());
            if(board[i][j]==1) queue.offer(new int[]{i,j});
         }
      }
 
      int max = 0;
      int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
      int[] now;
      int ni,nj,val;
      while(!queue.isEmpty()){
         now = queue.poll();
         val = board[now[0]][now[1]];
         max = Math.max(max,val);
 
         for(int[] d:deltas){
            ni = now[0]+d[0];
            nj = now[1]+d[1];
            if(ni<0||nj<0||ni>=N||nj>=M ||board[ni][nj]!=0) continue;
            board[ni][nj] = val+1;
            queue.offer(new int[]{ni,nj});
         }
      }
 
      System.out.println(max-1);
   }
}

---

3. 결과