[백준] [17086] 아기상어 2 (BFS) (JAVA)

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

17086번: 아기 상어 2

---

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

2

예제 입력 2 복사

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2 복사

2

---

※ JAVA 코드 (아기상어 2)

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

public class Main {
	static int N, M, result;
	
	static int[][] map;
	static boolean[][] visited;
	
	// 상하좌우 대각
	static int[] dx = {-1, -1, 0, 1, 1,  1,  0, -1};
	static int[] dy = { 0,  1, 1, 1, 0, -1, -1, -1};
	
	// 좌표를 담을 클래스
	public static class Node {
		int x, y, dist;
		public Node(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
	
	// 탐색
	public static int bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y, 0));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int i = 0; i < 8; i++) {
				int nextX = now.x + dx[i];
				int nextY = now.y + dy[i];
				
				if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}
				
				if(visited[nextX][nextY] == true) {
					continue;
				}
				
				if(map[nextX][nextY] == 1) {
					return now.dist + 1;
				}
				
				visited[nextX][nextY] = true;
				q.offer(new Node(nextX, nextY, now.dist + 1));
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visited = new boolean[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());
			}
		}
		
		result = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					visited = new boolean[N][M];
					result = Math.max(result, bfs(i, j));
				}
			}
		}
		
		System.out.println(result);
	}
}

---

※ 생각정리(아기상어 2)

1. 상어의 위치를 찾는다.

2. 방문체크 배열을 초기화하고 BFS탐색을 시작한다.

3. 이동한 만큼의 거리를 Node클래스에 담는다.

4. 다른 상어를 발견하면 이동한 거리 + 1을 하여 리턴한다.

5. 다른 상어를 발견하지 못하였다면 0을 리턴한다.

 

-새벽코딩-