백준 17086번 : 아기 상어 2(Java)

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

17086번: 아기 상어 2

---

[풀이]

 

• BFS를 이용해서 풀었습니다.
• 시작점을 큐에 넣은 이후, dis 배열에 거리에 대한 최소값을 저장하면서 계산합니다.
• 입력값을 받을 때 1이 있는 곳이 아기상어가 있는 칸이므로, 처음에 이 부분에 대해서만 큐에 담습니다.

---

[코드]

 

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 {

    static class Node {
        int x, y;

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

    static int N, M;
    static int[][] arr, dis;
    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());
        arr = new int[N][M];
        dis = new int[N][M];
        Queue<Node> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int input = Integer.parseInt(st.nextToken());
                arr[i][j] = input;
                dis[i][j] = Integer.MAX_VALUE;
                if (input == 1) {
                    queue.add(new Node(i, j));
                    dis[i][j] = 0;
                }
            }
        }
        int answer = 0;

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            for (int i = 0; i < 8; i++) {
                int next_x = now.x + dx[i];
                int next_y = now.y + dy[i];

                if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M) {
                    if (dis[next_x][next_y] > dis[now.x][now.y] + 1) {
                        dis[next_x][next_y] = dis[now.x][now.y] + 1;
                        queue.add(new Node(next_x, next_y));
                        answer = Math.max(answer, dis[next_x][next_y]);
                    }
                }
            }
        }
        System.out.println(answer);
    }
}