[Algo] 백준 17086 아기 상어2 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/17086

메모리 : 176080KB

시간 : 520ms

언어 : Java 11

---

코드

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 r, c, len;

        Node(int r, int c, int len) {
            this.r = r;
            this.c = c;
            this.len = len;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] 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[][] vector = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) { //빈땅일때
                    Queue<Node> q = new LinkedList<>();
                    boolean[][] check = new boolean[N][M];
                    q.add(new Node(i, j, 0));
                    check[i][j] = true;
                    //bfs
                    loop: while (!q.isEmpty()) {
                        Node n = q.poll();
                        for (int k = 0; k < 8; k++) {
                            int x = n.r + vector[k][0];
                            int y = n.c + vector[k][1];
                            if (x >= 0 && y >= 0 && x < N && y < M && !check[x][y]) {
                                if (map[x][y] == 1) {
                                    //안전거리 최댓값
                                    ans = Math.max(ans, n.len + 1);
                                    break loop;
                                }
                                check[x][y] = true;
                                q.add(new Node(x, y, n.len + 1));
                            }
                        }
                    }
                }

            }
        }
        System.out.println(ans);
    }
}

풀이

귀여운 BFS문제! 상어가 없는 빈 땅에서 가장 가까운 상어를 찾으면 값의 최대를 찾는다.