[백준 2468] 안전 영역 - JAVA

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

 

bfs

 

v[][] <- 잠긴 곳

w[][] <- 안전한 영역

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[][] a = new int[N][N];
    boolean[][] v = new boolean[N][N];
    StringTokenizer st;

    int[] dr = {0, 0, -1, 1};
    int[] dc = {-1, 1, 0, 0};

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        a[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    int ans = 1; // 아무 곳도 안잠긴 경우
    for (int h = 1; h <= 100; h++) {

      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (!v[i][j] && a[i][j] <= h) {
            v[i][j] = true;
          }
        }
      }

      boolean[][] w = new boolean[N][N];
      int cnt = 0;

      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (!v[i][j] && !w[i][j]) {
            cnt++;
            w[i][j] = true;
            Queue<int[]> q = new ArrayDeque<>();
            q.offer(new int[]{i, j});

            while (!q.isEmpty()) {

              int[] cur = q.poll();
              int r = cur[0];
              int c = cur[1];
              for (int k = 0; k < 4; k++) {
                int tr = dr[k] + r;
                int tc = dc[k] + c;
                if (tr >= 0 && tr < N && tc >= 0 && tc < N && !v[tr][tc] && !w[tr][tc]) {
                  w[tr][tc] = true;
                  q.offer(new int[]{tr, tc});
                }
              }
            }
          }
        }
      }

      ans = Math.max(ans, cnt);
    }

    System.out.println(ans);
  }
}