[백준] 17086 - 아기 상어2

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력

2

 

풀이 방법

문제를 대충 읽고 풀다가 틀렸다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다.

1. 모든 칸을 돌며 0인경우에 bfs를 이용 1과 가장 가까운 거리를 구했다.

2. 각 칸 별 안전거리 중 가장 큰 값을 출력

 

 

내 코드

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 Main_2206 {
	static int N, M, min=Integer.MAX_VALUE;
	static char[][] map;
	
	static class Node{
		int y, x, depth;
		boolean broken;
		
		public Node(int y, int x, int depth, boolean broken) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
			this.broken = broken;
		}
	}
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};

	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 char[N][];
		
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		Queue<Node> queue = new LinkedList<>();
		boolean[][][] visited = new boolean[N][M][2];
		
		queue.offer(new Node(0,0,1,false));
		visited[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			
			if(cur.y==N-1 && cur.x==M-1)
				min = Math.min(min, cur.depth);
			
			for (int d = 0; d < 4; d++) {
				int ny = cur.y + dy[d];
				int nx = cur.x + dx[d];
				
				if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
				
				if(map[ny][nx]=='0') {	//벽이 아닐 때
					if(!cur.broken && !visited[ny][nx][0]) { 	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,false));
						visited[ny][nx][0] = true;
					} 
					else if(cur.broken && !visited[ny][nx][1]) {	//지금까지 부순 벽이 있다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
				} else {	//벽일 때
					if(!cur.broken) {	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
					
				}
			}
		}

		if(min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
		
		br.close();

	}
}