[백준] | JAVA, 자바 | 2468번 - 안전 영역

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

---

문제 요약 :

1. 2차원 배열의 행과 열의 개수를 나타내는 수 N 입력받기

2. N번째 행까지 순서대로 한 행씩 높이 정보 입력받기

3. 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다.

4. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성

---

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

public class Main {
    private static int n;
    private static int[][] map;
    private static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 2차원 배열의 행과 열의 개수를 나타내는 수 N 입력받기
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int max = Integer.MIN_VALUE;
        // 2. N번째 행까지 순서대로 한 행씩 높이 정보 입력받기
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(max, map[i][j]);
            }
        }

        // 아무 지역도 잠기지 않았을 때 안전한 영역은 1개가 있기 때문에 기본값으로 1 설정
        int resultMax = 1;
        for(int i = 0; i < max; i++) {
            visited = new boolean[n][n];
            int result = 0;
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    if(!visited[j][k] && map[j][k] > i) {
                        visited[j][k] = true;
                        result++;
                        search(i, j, k);
                    }
                }
            }

            // 4. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산
            if(result > resultMax) resultMax = result;
        }
        // 최대 개수 출력
        System.out.println(resultMax);
    }

    // 3. 물에 잠기지 않는 안전한 영역 탐색
    private static void search(int check, int x, int y) {
        // 방문했거나 높이가 낮거나 같다면 return
        if(visited[x][y] && map[x][y] <= check) return;

        int[][] delta = {{1,0},{-1,0},{0,1},{0,-1}};

        for(int i = 0; i < 4; i++) {
            int nr = x + delta[i][0];
            int nc = y + delta[i][1];

            if(isRange(nr, nc) && !visited[nr][nc] && map[nr][nc] > check) {
                visited[nr][nc] = true;
                search(check, nr, nc);
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < n && nc >= 0 && nc < n;
    }
}