[백준/자바] 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

---

설명

bfs문제다.

상어 위치에서 8방향으로 돌리고 거리를 측정하면 된다.

다 측정을 마치고 거리가 가장 최대가 되는 값을 찾으면 된다.

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	public class BOJ17086 {
	static int safeZone[][];
	static int n;
	static int m;
	static ArrayList<String> shark = new ArrayList<>();
	static int dxy[][] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	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());
	safeZone = new int[n][m];
	int result = 0;
	for(int i = 0; i < n; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j = 0; j < m; j++) {
	if(Integer.parseInt(st.nextToken()) == 1) {
	shark.add(i+" "+j);
	}
	}
	}
	for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
	safeZone[i][j] = Integer.MAX_VALUE;
	}
	}
	for(String s:shark) {
	move(s);
	}
	for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
	result = Math.max(result, safeZone[i][j]);
	}
	}
	System.out.println(result);
	}
	static void move(String baby) {
	String str[] = baby.split(" ");
	int x = Integer.parseInt(str[0]);
	int y = Integer.parseInt(str[1]);
	safeZone[x][y] = 0;
	Queue<String> q = new LinkedList<>();
	q.add(baby);
	boolean visited[][] = new boolean[n][m];
	while(!q.isEmpty()) {
	String cur[] = q.poll().split(" ");
	int cx = Integer.parseInt(cur[0]);
	int cy = Integer.parseInt(cur[1]);
	visited[cx][cy] = true;
	for(int i = 0; i < 8; i++) {
	int tx = cx + dxy[i][0];
	int ty = cy + dxy[i][1];
	if(!isRange(tx, ty)) continue;
	if(visited[tx][ty]) continue;
	if(safeZone[cx][cy] + 1 <= safeZone[tx][ty]) {
	safeZone[tx][ty] = safeZone[cx][cy] + 1;
	q.add(tx+" "+ty);
	}
	}
	}
	}
	static boolean isRange(int x, int y) {
	return -1 < x && x < n && -1 < y && y < m;
	}
	}

view raw BOJ17086.java hosted with ❤ by GitHub