[백준(Baekjoon)] 17086. 아기 상어 2

 

[백준(Baekjoon)] 17086. 아기 상어 2

 

 

17086번: 아기 상어 2

 

 

 

[입력]

 

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

 

 

[출력]

 

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

 

 

[풀이]

 

문제를 보자마자 BFS가 생각났는데 변형하는 과정에서 조금 버벅였다.

8방탐색하며 거리마다 1씩 더해주는 식으로 arr에 저장하고 그 중 가장 큰 수를 찾아 -1을 해주었다.

 

 

원본 배열

0	0	1	0
0	0	0	0
1	0	0	0
0	0	0	0
0	0	0	1

 

 

bfs 후 

3	2	1	2
2	2	2	2
1	2	3	3
2	2	2	2
3	3	2	1

 

 

 

[코드]

 

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

public class bj17086 {

	static int[][] d = {
			{-1,-1},{-1,0},{-1,1},
			{0,-1},{0,1},
			{1,-1},{1,0},{1,1}}; //8방탐색
	static Queue<int[]> q;
	static boolean[][] isVisited; //방문여부
	static int N,M;
	static int[][] arr; //배열
	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());
		arr = new int[N][M];
		q = new LinkedList<>();
		isVisited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] == 1) {
					q.offer(new int[] {i,j}); //상어가 있는 인덱스만 큐에 저장
				}
			}
		}
		
		safe();
		
		int max = Integer.MIN_VALUE;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(arr[i][j] > 1) {
					max = Math.max(max, arr[i][j]);
				}
			}
		}
		System.out.println(max-1);

	}
	
	private static void safe() { //bfs
		
		while(!q.isEmpty()) { //큐가 비어있을때까지 반복
			int[] shark = q.poll(); //인덱스꺼냄
			int x = shark[0];
			int y = shark[1];
			
			for (int k = 0; k < d.length; k++) { //8방탐색
				int nr = x + d[k][0];
				int nc = y + d[k][1];
                
                //배열안에 존재하고 방문하지 않았을때
				if(nr >= 0 && nc >= 0 && nr < N && nc < M && !isVisited[nr][nc]) { 
					isVisited[nr][nc] = true; //방문 표시
					if(arr[nr][nc] == 0) { //1은 상어있는 자리니까 0일때만
						arr[nr][nc] = arr[x][y]+1; //이전 거리에 더하여 거리 저장
						q.offer(new int[] {nr,nc}); //현위치 인덱스를 큐에 삽입
					}
				}
			}
		}
	}

}