아기 상어 2 - 17086

문제

풀이

import java.util.*;

// 아기상어2 - BFS
class Point5{
    int x;
    int y;
    public Point5(int x,int y) {
        this.x = x;
        this.y = y;
    }
}
public class ex17086 {
    static int n,m,answer=Integer.MIN_VALUE;
    static int[][] board;
    static int[] dx={0,1,1,1,0,-1,-1,-1};
    static int[] dy={1,1,0,-1,-1,-1,0,1};
    static int[][] dis;
    static boolean[][] ch;
    public static void BFS(int x,int y,int[][] dis,boolean[][] ch){
        Queue<Point5> Q = new LinkedList<>();
        Q.offer(new Point5(x,y));
        ch[x][y]=true;

        while(!Q.isEmpty()){
            Point5 poll = Q.poll();
			
            if(board[poll.x][poll.y]==1){
                answer = Math.max(answer,dis[poll.x][poll.y]); //핵심
                break;
            }

            for(int i=0; i<8; i++){
                int nx = poll.x + dx[i];
                int ny = poll.y + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m && !ch[nx][ny]){
                    ch[nx][ny]=true;
                    Q.offer(new Point5(nx,ny));
                    dis[nx][ny] = dis[poll.x][poll.y] + 1;
                }
            }
        }
    }
    public static void solution(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]==0){
                    dis = new int[n][m];
                    ch = new boolean[n][m];
                    BFS(i,j,dis,ch);
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                board[i][j] = sc.nextInt();
            }
        }
        solution();
        System.out.println(answer);
    }
}

글 목적
이 문제는 한번에 맞췄다!
근데 이 글을 쓰는 목적은 기본적인 문제라 나중에 복습을 하기 위함.

우선 기본적인 BFS 템플릿 구조를 가진다. 하지만 주의할점은 8방향으로 대각선 포함 이동이 가능해야하며, 각 위치(좌표)에서의 상어까지의 최소거리를 구해서, 모든 좌표에서 가장 긴 상어까지의 길이 answer를 출력하는게 핵심이다.

우선 각 좌표를 구해서 BFS()를 돌릴 solution()를 구현해준다. 이 때 주의할 점은 dis[][] 거리 좌표배열과 ch[][] 체크 불리언 배열을 초기화 시켜서 BFS()에 같이 보내줘야한다.

그 후 메인 BFS()에서 기본적인 BFS()템플릿 구조대로 구현을 하돼,

	if(board[poll.x][poll.y]==1){
        answer = Math.max(answer,dis[poll.x][poll.y]); //핵심
        break;
	}

이 구문을 이용해서 각 좌표의 상어까지의 최소거리들 중에서 가장 긴 최대거리를 구한다.