Baekjoon 17086 아기 상어 2 JAVA

17086번: 아기 상어 2

문제

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

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

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

조건

[입력]

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

 

[출력]

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

풀이

해당 문제는 상어로부터 거리가 가장 먼 칸의 거리를 구하는 문제다. bfs를 이용하여 쉽게 해결할 수 있었다. 아래와 같은 로직으로 구현하였다.

1. 입력처리를 하면서 상어의 위치를 큐에 담는다.

2. bfs를 큐가 빌 때까지 돌린다.

 2-1. 8방 탐색을 하는데 배열의 범위 밖이면 다음 반복을 진행한다.

 2-2. 이미 방문했거나(cnt[ny][nx] != 0) 가려는 곳이 상어이면 다음 반복을 진행한다.

3. 방문 가능하면 cnt 배열을 갱신하고 큐에 넣어준 다음 ans에 최댓값을 갱신하여준다.

코드

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

public class Main {

	static int N, M, ans, dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 }, dy[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
	static int[][] map, cnt;
	static Queue<Node> q = new LinkedList<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		cnt = new int[N][M];
		
		for (int i = 0; i < N; i++) { // 입력 처리하면서 상어의 위치를 큐에 담음
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					q.add(new Node(i, j));
				}
			}
		}
		bfs();
		System.out.println(ans);
	}

	private static void bfs() {// 상어들을 빼내면서 갈수있는애들을 카운트 증가시켜줌
		while (!q.isEmpty()) {
			Node n = q.poll();
			for (int i = 0; i < 8; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if (ny < 0 || nx < 0 || ny >= N || nx >= M) 
					continue;
				if (cnt[ny][nx] != 0 || map[ny][nx] == 1)
					continue;
				cnt[ny][nx] = cnt[n.y][n.x] + 1;
				q.add(new Node(ny, nx));
				ans = Math.max(ans, cnt[ny][nx]);
			}
		}
	}

	static class Node {
		int y, x;
		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드