문제 설명

17086번: 아기 상어 2

안전거리 값이 가장 큰 것을 출력하면 된다.

안전거리는 상어가 도달하기까지 걸리는 시간을 의미한다.

상어는 8방으로 이동할 수 있다.

접근

전형적인 BFS 문제이다. 상어의 초기 위치를 queue에 삽입하고, 도달할 수 있는 가장 가까운 위치부터 차근차근 이동한 후 가장 마지막 도착한 곳의 안전거리를 출력하면 된다.

public class Main {
	// 8방 탐색을 위해 아래와 같이 셋팅함
	public static int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
	public static int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		// map은 지도 역할 & 방문 여부를 체크하는데 사용
		boolean[][] map = new boolean[N+2][M+2];
		Queue<int[]> queue = new LinkedList<int[]>();
		
		for(int n=1; n<=N; n++) {
			st = new StringTokenizer(br.readLine());
			for(int m=1; m<=M; m++) {
				boolean area = Integer.parseInt(st.nextToken())==0 ? true : false;
				map[n][m] = area;
				if(!area)  // 상어인 경우 queue에 일단 삽입
					queue.add(new int[] {n, m, 0});
			}
		}
		int answer = 0;
		while(!queue.isEmpty()) {
			int[] temp = queue.poll();    // 0: n, 1: m, 2: 안전거리
			int r = temp[0], c = temp[1];
			answer = Math.max(answer, temp[2]); // 최신값으로 업데이트
			
			for(int i=0; i<8; i++) {     // 8방 탐색
				if(!map[r+dr[i]][c+dc[i]]) continue;  // 이미 방문한적이 있으면 제외
				queue.add(new int[] {r+dr[i], c+dc[i], temp[2]+1});
				map[r+dr[i]][c+dc[i]] = false;        // 방문결정됐으므로 중복방지 위해 표시
			}
		}
		
		System.out.println(answer);
	}
}

소스코드

최종적으로 제출한 코드는 다음과 같다.

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

public class Main {
	public static int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
	public static int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		boolean[][] map = new boolean[N+2][M+2];
		Queue<int[]> queue = new LinkedList<int[]>();
		
		for(int n=1; n<=N; n++) {
			st = new StringTokenizer(br.readLine());
			for(int m=1; m<=M; m++) {
				boolean area = Integer.parseInt(st.nextToken())==0 ? true : false;
				map[n][m] = area;
				if(!area)
					queue.add(new int[] {n, m, 0});
			}
		}
		int answer = 0;
		while(!queue.isEmpty()) {
			int[] temp = queue.poll();
			int r = temp[0], c = temp[1];
			answer = Math.max(answer, temp[2]);
			
			for(int i=0; i<8; i++) {
				if(!map[r+dr[i]][c+dc[i]]) continue;
				queue.add(new int[] {r+dr[i], c+dc[i], temp[2]+1});
				map[r+dr[i]][c+dc[i]] = false;
			}
		}
		
		System.out.println(answer);
	}
}

결과

고찰

bfs는 그래도 이전에 공부한 것이 있어서 그런지 매우 익숙해서 괜찮았다!