[Java] 백준 17086번 : 아기 상어 2

문제

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

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

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

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제 입력 1

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

 

소스코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N, M, maxVal=0;
	private static int [][] map;
	private static int [][] visited;
	private static Queue<Point> queue=new LinkedList<>();
	private static int [] dx = {-1,-1,-1,1,1,1,0,0};
	private static int [] dy = {-1,0,1,-1,0,1,-1,1};
	
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		visited=new int[N][M];
		
		for(int r=0;r<N;r++) {
			st=new StringTokenizer(bf.readLine());
			for(int c=0;c<M;c++) {
				map[r][c]=Integer.parseInt(st.nextToken());
				visited[r][c]=Integer.MAX_VALUE;
				if(map[r][c]==1) {	// 아기 상어의 위치를 모두 queue에 넣음
					queue.offer(new Point(r, c));
					visited[r][c]=0;	// 아기 상어의 거리를 0으로 설정
				}
			}
		}
		
		bfs();	// 안전 거리 탐색
		System.out.println(maxVal);
	}
	
	public static void bfs() {
		
		while(!queue.isEmpty()) {
			Point p=queue.poll();
			
			for(int i=0;i<8;i++) {
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				if(isIn(nx, ny)) {
					if(visited[nx][ny]>visited[p.x][p.y]+1) {	// 아기 상어의 안전 거리 계산(최소)
						visited[nx][ny]=visited[p.x][p.y]+1;
						maxVal=Math.max(maxVal, visited[nx][ny]);	// 안전 거리 중 최대값 maxVal에 저장
						queue.offer(new Point(nx, ny));
					}
				}
			}
		}
	}
	
	public static boolean isIn(int r, int c) {
		return r>=0 && r<N && c>=0 && c<M;
	}
}

문제를 이해하지 못해서 한참 헤맸었습니다. 

1. 안전 거리 : 한 아기 상어로부터 다른 아기 상어까지의 최소 거리

2. 구하는 값 : 안전 거리들 중 최댓값