[BOJ] 백준 17086 - 아기 상어 2 풀이

1. 문제

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

17086번: 아기 상어 2

 

2. 풀이

BFS 문제이다.
처음 문제를 읽고, 예제 입력을 봤을 때는 무슨 말인지 이해가 안됬지만, 예제를 하나씩 따라가다 보면 충분히 이해할 수 있는 문제였다.

우선 점의 x, y 좌표와 그 점까지의 거리값을 넣을 static class를 하나 선언해준다.
그 다음 입력을 받고 점들을 반복문으로 탐색하면서 1이 아닌 0인 점부터 bfs 탐색을 시작한다. 1인 부분은 상어가 있는 부분이기에 탐색 시작에서 제외한다. (이 부분이 처음에 엄청 헷갈렸다.)

bfs 탐색을 돌리면서 다음 점이 1이 나오면 상어를 찾은 것이므로, 리턴하여 값을 비교한 후 거리를 갱신한다.

 

3. 소스 코드

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

public class Main {
    static class Point {
        int x;
        int y;
        int dist;

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

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

    static int result = 0;

    static int[][] map;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {
                    continue;
                }

                int tempResult = bfs_shark2(i, j);
                result = Math.max(tempResult, result);
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static int bfs_shark2(int row, int col) {
        visited = new boolean[N][M];
        visited[row][col] = true;

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(row, col, 0));

        while (!queue.isEmpty()) {
            Point poll = queue.poll();

            for (int i = 0; i < 8; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];
                int newDist = poll.dist + 1;

                if (xf < 0 || yf < 0 || xf >= N || yf >= M || visited[xf][yf]) {
                    continue;
                }

                if (map[xf][yf] == 1) {
                    return newDist;
                }

                queue.offer(new Point(xf, yf, newDist));
                visited[xf][yf] = true;
            }
        }
        return 0;
    }
}