[백준/JAVA] BOJ 17086 - 아기 상어 2

👀 문제

17086번: 연구소 ✨ 실버 2

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

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

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

예제 입력

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

예제 출력

2

🔑 키포인트

너비 우선 탐색 그래프 이론 그래프 탐색

✍️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int m;
	static int[][] shark;
	static Queue<int[]> queue;
	
	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());
		
		shark = new int[n][m];
		queue = new LinkedList<int[]>();
		
		// 배열 입력받기 
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				shark[i][j] = Integer.parseInt(st.nextToken());
				
				// 상어면 넣기 
				if (shark[i][j] == 1) {
					queue.offer(new int[] {i, j});
				}
			}
		}
		
		bfs();
		
		int result = 0;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				result = Math.max(shark[i][j], result);
			}
		}
		
		System.out.println(result-1);
	}
	
	public static void bfs() {
		int[] dx = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };
		
		while (!queue.isEmpty()) {
			
			// 현재 위치 
			int[] where = queue.poll();
			
			// 8방향 탐색 
			for (int i = 0; i < 8; i++) {				
				int nx = where[0] + dx[i];
				int ny = where[1] + dy[i];
				
				if (0 <= nx && nx < n && 0 <= ny && ny < m) {
					if (shark[nx][ny] == 0) {
						shark[nx][ny] = shark[where[0]][where[1]] + 1;
						queue.offer(new int[] {nx, ny});
					}
				}
			}
		}
	}
}