[Algorithm /백준] 17086 아기 상어 2

[문제]
N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

[입력]
첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

[출력]
첫째 줄에 안전 거리의 최댓값을 출력한다.

 

[문제 해결 - BFS]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
    static int[][] arr;
    static boolean[][] visited;
    //대각선거리 1까지의 좌표
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static int N, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
            	arr[i][j] = sc.nextInt();
            }
        }

        int maxResult = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    visited = new boolean[N][M];
                    maxResult = Math.max(maxResult, bfs(new PointSpot(i, j)));
                }
            }
        }

        System.out.println(maxResult);
    }

    static int bfs(PointSpot start) {
        Queue<PointSpot> queue = new LinkedList<>();
        queue.offer(start);
        visited[start.x][start.y] = true;

        int distance = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int k = 0; k < size; k++) {
                PointSpot p = queue.poll();

                for (int i = 0; i < 8; i++) {
                    int nextX = p.x + dx[i];
                    int nextY = p.y + dy[i];

                    if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length)
                        continue;
                    if (visited[nextX][nextY])
                        continue;
                    visited[nextX][nextY] = true;

                    //상어를 만난 경우
                    if (arr[nextX][nextY] == 1) {
                        return distance + 1;
                    }

                    queue.add(new PointSpot(nextX, nextY));
                }
            }
            //거리 증가 시키기
            distance++;
        }

        return 0;
    }
}
class PointSpot {
    int x;
    int y;

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

 

 

 

+) 문제를 푸는 시간보다 문제를 이해하는 시간이 더많이 걸렸던 문제!

코린이라 그런지 정말 한참을 헤매였던.... :)

 

삼성의 유형으로 유명하던데 몇가지 유형으로 더 연습해봐야겠다는 생각이들었다!