[BOJ] 2468. 안전영역 - JAVA 자바

2468번: 안전 영역

💡 DFS 

 

비 내리는 양에 따라 나뉜 영역 개수를 찾고 그 중 가장 많은 영역을 가질 수 있는 경우를 구하면 되는 문제이다. (0,0)부터 상하좌우로 탐색하며 방문 체크하는 구조로 DFS를 이용했다.

• max_rain : 비가 올 수 있는 최대 ( 지역의 높이 중 가장 큰 높이 )

비 내리는 양을 하나씩 증가시키며 나뉜 영역 중 최대 구하기

1. 비 양에 따른 물에 잠긴 구역 체크 full()
2. 이중 for문을 돌며 물에 잠기지 않은 구역 탐색 safe_area()
3. 물에 잠기지 않은 구역 발견 시, 해당 구역을 출발점으로 상하좌우 탐색하며 체크 DFS()
4. 기존의 max값과 비교 후, 더 많은 영역을 가질 수 있다면 max값 change solution()
5. 이 후, 비 내리는 양 증가 ➜ 다시 1번 반복

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

public class Main {
    static int N;
    static int[][] board;
    static boolean[][] check;      // 체크한 구역인지 
    static int[] distX = { -1, 1, 0, 0 };
    static int[] distY = { 0, 0, 1, -1 };
    static int max = 0, count = 0;
    static int max_rain = 0;       // 최대로 올 수 있는 비 양 

    // 물에 잠긴 구역 체크 
    public void full(int rain) {
        if (rain == 0) {
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                check[i][j] = false;  // 저번 비 양의 체크한 구역을 다시 false로 되돌리기
                if (board[i][j] <= rain) {
                    check[i][j] = true;
                }
            }
        }
    }

    // 출발점과 동일한 안전 구역 체크 
    public void DFS(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int dx = x + distX[i];
            int dy = y + distY[i];

            if (dx >= 0 && dx < N && dy >= 0 && dy < N) {
                if (!check[dx][dy]) {
                    check[dx][dy] = true;
                    DFS(dx, dy);
                }
            }
        }
    }

    // 안전구역의 출발점 찾기 
    public int safe_area(int rain) {
        full(rain);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!check[i][j]) {
                    count++;            // 안전 구역 발견 
                    check[i][j] = true; // 해당 구역을 출발점으로 동일한 구역의 칸 체크 
                    DFS(i, j);
                }
            }
        }
        return count;
    }

    // 비의 양에 따른 최대 안전 구역 개수 찾기 
    public void solution(int rain) {
        while (rain < max_rain) {
            max = Math.max(safe_area(rain++), max);
            count = 0;
        }
    }

    public static void main(String[] args) throws IOException {
        Main M = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        M.solution(0);
        System.out.println(max);
    }
}