[java] 17086 아기 상어2

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

처음에 1부터 1까지의 거리인 줄 알았는데,
맵의 수많은 0부터 1까지의 거리였다. 그 중 최장거리를 구하는 문제

1. 반복문 돌리다 0일 때 BFS
2. 1이 나오면 거리 return

3. 코드

import java.util.*;
import java.io.*;
import java.awt.Point;

class Node{
	int x,y,dist;
	Node(int x, int y, int dist){
		this.x = x;
		this.y = y;
		this.dist = dist;
	}
}

public class Main{

	static int N,M,result;
	static int[][] arr;
	static boolean[][] visited;
	static int[] dx = {1,0,-1,0,-1,-1,1,1};
	static int[] dy = {0,1,0,-1,-1,1,-1,1};

	public static void main(String args[]) throws Exception{
        
        // 값 입력 -->
        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]; 
		
		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());
		}
        // <--

		result = -1; // 최댓값 max을 구해야 하므로, -1

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
				if(arr[i][j] == 0){ // 0부터 1까지의 최장거리 이므로, 0 일 때 BFS
					visited = new boolean[N][M]; // 매 0 마다 새로운 거리를 탐색해야 하므로 초기화
					BFS(i,j); // 최장거리를 구해야 하므로 BFS 탐색
				} 
			}
		}
		System.out.println(result);
	}

	public static void BFS(int i, int j){
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(i,j,0));
		visited[i][j] = true;

		while(!q.isEmpty()){
			Node now = q.poll();
			int x= now.x;
			for(int k=0;k<8;k++){
				int xx = now.x + dx[k];
				int yy = now.y + dy[k];

				if(xx<0 || xx>=N || yy<0 || yy>=M || visited[xx][yy]) continue;
                visited[xx][yy] = true;
                if(arr[xx][yy] == 1) { // 1이 나오면 현재 거리 +1 을 리턴 
					result = Math.max(result, now.dist+1);
					return;
				}
				q.offer(new Node(xx,yy,now.dist+1)); // 0일 때 거리 +1 로 Q 추가
				
			}
		}
		

	}
}