BOJ 2468 안전 영역

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

/***
 * 시간제한: 1초, 메모리제한:128MB
 * 2<=N<=100, 1<=h<=100 -> 100 * 100 * 100 -> 1,000,000 -> 3중 for문 가능.
 * 아이디어: 입력을 받으며 최대높이 h를 구하고, 1부터 h까지 bfs를 반복하며 안전한 영역 최대 개수 값을 갱신해 나간다.
 * water 1부터 h까지 반복한다.
 * 1. 방문 처리 배열 초기화.
 * 2. bfs 를 수행하며 water보다 높은 곳만 방문한다.
 * 3. bfs 를 수행한 후 안정한 영역의 최대 개수 값을 갱신한다.
 * 4. water 를 1증가 시킨다.
 */
public class Main {
    // 동, 서, 남, 북
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    static int N, water, h, res;
    static int[][] srcMap;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        // 1. 입력 받기.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

        // 2. 자료형 준비.
        res = 0; // 안전한 영역
        water = 0; // 장마철 물 높이.

        // 3. 처리
        while(water <= h){
            // 3-1. bfs 처리 전 방문 배열 및 cnt 초기화.
            int cnt = 0;
            visited = new boolean[N][N];

            // 3-2. bfs 수행
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(!visited[i][j] && srcMap[i][j] > water){
                        bfs(i, j, water);
                        cnt++;
                    }
                }
            }

            res = Math.max(res, cnt);

            // 3-2.
            water++;
        }

        // 4. 출력
        System.out.println(res);
    }

    static void bfs(int startY, int startX, int water){
        visited[startY][startX] = true;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startY, startX});

        while(!queue.isEmpty()){
            int[] items = queue.poll();
            int y = items[0];
            int x = items[1];

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

                if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

                if(!visited[ny][nx] && srcMap[ny][nx] > water){
                    visited[ny][nx] = true;
                    queue.offer(new int[]{ny, nx});
                }
            }
        }
    }
}