문제 풀이(66)

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

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

/**
5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
 */
class Point{
    int x;
    int y;

    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {

    static int N, M;

    static int[][] board, dist;

    static int[] dx = {-1, 1, 0, 0, 1, 1, -1, -1};
    static int[] dy = {0, 0, 1, -1, 1, -1, 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());

        board = new int[N][M];

        dist = new int[N][M];

        Queue<Point> Q = new LinkedList<>();

        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
            
                board[i][j] = Integer.parseInt(st.nextToken());
                dist[i][j] = Integer.MAX_VALUE;

                if (board[i][j] == 1) {
                    Q.offer(new Point(i, j));
                    dist[i][j] = 0;
                }

            }
        }

        int answer = 0;

        while (!Q.isEmpty()) {
            
            Point now = Q.poll();

            for (int k = 0; k < 8; k++) {
                
                int nx = now.x + dx[k];
                int ny = now.y + dy[k];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
                    continue;
                }

                if (dist[nx][ny] > dist[now.x][now.y] + 1) {
                    dist[nx][ny] = dist[now.x][now.y] + 1;
                    Q.offer(new Point(nx, ny));
                    answer = Math.max(answer, dist[nx][ny]);
                }
            }
        }

        System.out.println(answer);
    }
}

2차원 격자에서 "1"로 표시된 점들로부터의 최대 거리를 찾는 자바 프로그램입니다. 각 점에서 8가지 방향(상, 하, 좌, 우, 대각선 4방향)으로 이동할 수 있으며, 각 이동은 거리를 1만큼 증가시킵니다. 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘을 사용하여 모든 점에서 도달할 수 있는 최대 거리를 계산합니다.