백준 17086번 <아기 상어2>

백준 알고리즘 17086번

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

17086번: 아기 상어 2

---

17086번

N * M 크기의 공간에 아기 상어가 여러 마리 있다. (아기 상어는 최대 1마리 존재한다.)

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 이때 이동은 인접한 8방향이 가능하다.

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

 

입력으로 첫 줄에 공간의 크기 N과 M이 들어오고 그 다음 줄 부터 공간의 정보가 들어온다.

 

출력으로 안전 거리의 최댓값을 출력하면 된다.

---

문제 해결

BFS를 이용하여 문제를 풀었다.

처음에 들어오는 아기 상어의 위치들을 큐에 넣어서 시작점으로 활용한다.

또한 while문 안에서 큐의 크기를 이용하여 for문을 돌리면 처음 for문은 진짜 아기 상어의 위치, 그 다음 for문을  아기 상어의 위치에서 1번 이동했을 때의 위치, 그 다음 for문은 2번 이동했을 때의 위치들을 순서대로 볼 수 있다.

입력으로 들어오는 map을 유지할 필요가 없기 때문에 방문체크에 활용했다. 방문을 했으면 1, 그렇지 않으면 0이 된다.

---

코드

package boj17086;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

/*
 * BFS를 이용하여 해결
 * 처음에 들어오는 아기 상어의 위치를 큐에 넣어준다.
 * 큐의 크기만큼 for문을 돌려서 -> 아기 상어들과 특정 거리만큼 떨어진 공간을 볼 수 있다.
 * 큐에 들어있는 위치들에서 다음에 갈 수 있는 공간을 찾아 큐에 넣는다.
 * 입력으로 들어오는 map을 유지할 필요가 없기 때문에 방문한 공간을 1로 만들어 방문 체크를 한다.
 * */

public class Main {
	static class Tuple {
		int i, j;

		public Tuple(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");

		int n = Integer.parseInt(inArr[0]);
		int m = Integer.parseInt(inArr[1]);
		Queue<Tuple> queue = new ArrayDeque<>();
		int[][] map = new int[n][m];
		for (int i = 0; i < n; i++) {
			inArr = br.readLine().split(" ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(inArr[j]);
				if (map[i][j] == 1) {
					queue.add(new Tuple(i, j));
				}
			}
		}

		int maxDist = -1;
		int[] di = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int[] dj = { 0, 0, -1, 1, -1, 1, -1, 1 };
		while (!queue.isEmpty()) {
			int size = queue.size();
			maxDist++;
			for (int i = 0; i < size; i++) {
				Tuple tp = queue.poll();
				for (int k = 0; k < 8; k++) {
					int ni = tp.i + di[k];
					int nj = tp.j + dj[k];
					if (ni < 0 || nj < 0 || ni >= n || nj >= m) {
						continue;
					}
					if (map[ni][nj] == 1) {
						continue;
					}

					map[ni][nj] = 1;
					queue.add(new Tuple(ni, nj));
				}
			}
		}
		System.out.println(maxDist);
	}
}

---

결과

---