[코테] 백준 2468 안전 영역: DFS Java

문제 설명이 좀... 아쉬운 부분이 많은 문제인 것 같다

 

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

 

- 안전한 영역 = 비에 잠기지 않고, 상하좌우로 인접해 있으면 한 영역이라고 본다

- 강수량 = 가장 많은 안전한 영역이 나오는 강수량을 찾아야 한다

 

전체 코드

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

public class baekjoon_2468 {

    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        int maxHeight = 0;
        // 값들 중 가장 큰 값을 maxHeight로 설정한다
        for (int i = 0; i < N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < N; j++) {
                maxHeight = Math.max(maxHeight, arr[i][j]);
            }
        }

        int maxSafeZone = 0;

        for (int rain = 0; rain <= maxHeight; rain++) { // 모든 강수량에 대해 검사
            visited = new boolean[N][N]; // 초기화, 각 '강수량' 마다 새롭게 분석을 해야하므로
            int safeCount = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && arr[i][j] > rain) {
                        dfs(i, j, rain);
                        safeCount++;
                    }
                }
            }

            maxSafeZone = Math.max(maxSafeZone, safeCount);
        }

        System.out.println(maxSafeZone);
        br.close();
    }

    private static void dfs(int y, int x, int rain) {
        visited[y][x] = true;

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

            if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
                if (!visited[ny][nx] && arr[ny][nx] > rain) {
                    dfs(ny, nx, rain);
                }
            }
        }
    }
}

 

dfs 함수 자체는 어렵지 않은데 문제 이해가 특히 어려웠다

강수량에 대한 설명이 잘 나와있지 않아서 아쉬웠다