[백준/자바] 17086번: 아기 상어 2

문제

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

풀이

• N*M 크기의 공간에 아기 상어 여러 마리 존재
• 한 칸에 한 마리만 존재
• 안전 거리란? 그 칸과 가장 거리가 가까운 아기 상어와의 거리
• 이동은 인접한 8방향 가능
• 안전 거리가 가장 큰 칸을 구하자

멀티 소스 BFS를 활용하면 되는 문제

	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1) {
					dist[i][j] = 0; // 탐색 시작 칸
					queue.add(new int[] {i, j}); // 아기 상어 좌표
				}
			}
		}
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			
            // 8방향 탐색
			for (int i = 0; i < 8; i++) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];
				
                // 범위 밖이면 pass
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
				// 방문하지 않은 칸이 아니라면 pass
                if (dist[nr][nc] != -1) continue;
				
				dist[nr][nc] = dist[r][c] + 1;
				queue.add(new int[] {nr, nc});
				if (answer < dist[nr][nc]) answer = dist[nr][nc];
			}
		}
	}

아기 상어를 기준으로 동시에 탐색을 시작합니다.

• 8방향을 탐색하면서 이미 이동한 전적이 있다면 지나칩니다.
• 방문하지 않은 칸이라면 이전 거리 + 1로 이동(큐에 삽입)
• 이동할 때마다 최댓값을 갱신하면 정답을 바로 구할 수 있습니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static int[][] map, dist;
	static int[][] dir;
	static int answer = 0;
	
	// 8방향 설정
	private static void makeDir() {
		dir = new int[8][2];
		int idx = 0;
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (i == 0 && j == 0) continue;
				dir[idx][0] = i;
				dir[idx++][1] = j;
			}
		}
	}
	
	private static void bfs() {
		Queue<int[]> queue = new ArrayDeque<>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1) {
					dist[i][j] = 0;
					queue.add(new int[] {i, j});
				}
			}
		}
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			
			for (int i = 0; i < 8; i++) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
				if (dist[nr][nc] != -1) continue;
				
				dist[nr][nc] = dist[r][c] + 1;
				queue.add(new int[] {nr, nc});
				if (answer < dist[nr][nc]) answer = dist[nr][nc];
			}
		}
	}
	
	
	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());
		
		map = new int[n][m];
		dist = 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());
				dist[i][j] = -1;
			}
		}
		
		makeDir();
		bfs();
		
		System.out.println(answer);
	}
}