[BOJ/BFS] 백준 17086 - 아기 상어 2 (Java)

17086 - 아기 상어 2

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

문제

NxM 크기의 공간에 아기 상어 여러 마리가 있음
공간은 1x1 크기의 정사각형 칸으로 나누어져 있고 한 칸에는 아기 상어 최대 1마리 존재
어떤 칸의 안전 거리는 그 칸과 가장 가까운 아기 상어와의 거리
두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함) 가능

=> 안전 거리가 가장 큰 칸?

입력
첫째 줄: 공간의 크기 N과 M (2 <= N, M <= 50)
둘째 줄 ~ N개의 줄: 공간의 상태 (0: 빈 칸 / 1: 아기 상어가 있는 칸)
빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어짐
출력: 안전 거리의 최댓값?

---

풀이

• 현재 좌표 (x, y)와 해당 지점까지 걸린 거리(dist) 저장용 클래스

class Point {
    int x, y, dist;

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

 

• 가로, 세로, 또는 대각선으로 이동 가능

static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

 

BFS

• 매 BFS마다 새롭게 방문 체크
  • `visited = new boolean[N][M]`
• (x, y) 지점에서 가장 가까운 1이 있는 칸까지의 최단 거리
  => BFS는 최단 거리 탐색에서 처음 도달한 순간이 무조건 최소 거리
  • 목표 지점(상어)를 찾으면, 현재 거리 `dist` 반환
    • `if (map[cur.x][cur.y] == 1) return cur.dist` 

static int bfs(int x, int y) {
    Queue<Point> q = new LinkedList<>();
    visited = new boolean[N][M];
    visited[x][y] = true;
    q.offer(new Point(x, y, 0));

    while (!q.isEmpty()) {
        Point cur = q.poll();

        if (map[cur.x][cur.y] == 1) return cur.dist;

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                q.offer(new Point(nx, ny, cur.dist + 1));
            }
        }
    }

    return 0;
}

---

코드

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

// 아기 상어 2
class Point {
    int x, y, dist;

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

public class boj_17086 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    static int bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[N][M];
        visited[x][y] = true;
        q.offer(new Point(x, y, 0));

        while (!q.isEmpty()) {
            Point cur = q.poll();

            if (map[cur.x][cur.y] == 1) return cur.dist;

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny, cur.dist + 1));
                }
            }
        }

        return 0;
    }

    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());

        map = new int[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());
            }
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    answer = Math.max(answer, bfs(i, j));
                }
            }
        }

        System.out.println(answer);
    }
}