[백준] 17086 - 아기 상어 2

[문제링크]

17086번: 아기 상어 2

 

0. 상어와 가장 먼 칸에서의 상어와의 거리를 구하는 문제

 

1. 이동 방향이 8방향이므로, dir 배열을 8방향으로 구성한다

 

2. 상어를 기준점으로 주변 칸을 bfs로 탐색한다

• 위치와 거리 정보를 저장하는 class를 만들어 사용한다
• 탐색하며 거리 정보를 칸에 저장한다
• 탐색 중 특정 지점에 현재 거리보다 작거나 같은 값이 저장되있다면, 다른 상어가 더 가깝게 있다는 뜻이므로 탐색을 정지한다

 

3. 모든 상어로부터 bfs가 종료되면, 가장 거리가 먼 칸을 탐색, 출력한다

 

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[][] dir = new int[][] {
		{1,0},{1,1},{0,1},{-1,1},
		{-1,0},{-1,-1},{0,-1},{1,-1}
	};
	static int[][] distanceMap;
	static int[][] map;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		map = new int[n][m];
		distanceMap = new int[n][m];
		
		for(int i = 0; i < map.length; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < map[0].length; j++) {
				map[i][j] = pint(st.nextToken());
				distanceMap[i][j] = Integer.MAX_VALUE;
			}
		}

		int ans = 0;
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[0].length; j++) {
				if(map[i][j]==1) {
					dfs(i,j);
				}
			}
		}

		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[0].length; j++) {
				if(ans<distanceMap[i][j])ans=distanceMap[i][j];
			}
		}
		System.out.println(ans);
	}
	
	static void dfs(int x, int y) {
		Queue<point>qu = new LinkedList<>(); 
		qu.offer(new point(x,y,0));
		distanceMap[x][y] = 0;
		
		while(!qu.isEmpty()) {
			point cur = qu.poll();
			
			for(int d=0;d<dir.length;d++) {
				int nx = cur.x + dir[d][0];
				int ny = cur.y + dir[d][1];
				int depth = cur.depth + 1;
				
				if(nx<0 || nx >= map.length || ny<0 || ny>=map[0].length || distanceMap[nx][ny]<=depth) {
					continue;
				}
				
				distanceMap[nx][ny] = depth;
				qu.offer(new point(nx,ny,depth));
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	

}

class point{
	int x;
	int y;
	int depth;
	public point(int x, int y, int depth) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
	}
}

결과 화면