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

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

---

📝 문제 설명

2차원 배열을 입력을 받는다. 이때 입력받는 값은 해당 영역의 높이다. 모두 입력받고 나서 최대 높이를 구해 0부터 이 높이까지 높여나가면서 각각의 높이일 때 안전 영역의 개수를 구한다.

이때, 안전영역이란 물에 잠기지 않은 영역을 말한다. 즉, 비의 양보다 높이가 높은 영역들이다. 각 높이에서의 이 영역을 구해 최댓값을 출력하면 된다.

✨ 제출 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, maxHeight;
    static int[][] graph;
    static boolean[][] visited;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

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

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

        maxHeight = 0; // 높이의 최댓값

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, graph[i][j]); // 최대 높이 갱신
            }
        }

        int maxSafeAreas = 0;

        // 강수량을 0부터 최대 높이까지 변화시키면서 안전 영역 계산
        for (int rain = 0; rain <= maxHeight; rain++) {
            visited = new boolean[N][N]; // 방문 배열 초기화
            int count = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 현재 위치가 침수되지 않았고, 방문하지 않은 경우 DFS 탐색
                    if (graph[i][j] > rain && !visited[i][j]) {
                        dfs(i, j, rain);
                        count++;
                    }
                }
            }

            maxSafeAreas = Math.max(maxSafeAreas, count); // 최대값 갱신
        }

        System.out.println(maxSafeAreas);
    }

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

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

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

 

✌️ 코드 설명

이 문제는 물에 잠기지 않고 인접해있는 영역의 개수를 구해야 하기 때문에 dfs를 이용했다. 먼저 2차원 배열을 입력받으면서 graph에 저장해 준다. 그러면서 영역의 최대 높이 또한 계산해 준다. 

그럼 이제 0부터 최대 높이의 강수량 까지 탐색할 거다. 각 높이마다 안전영역의 개수를 구할 것이기 때문에 visited배열은 매 for문마다 초기화해주었다. count변수 또한 마찬가지다. 해당 칸의 높이가 강수량보다 커서 잠기지 않고 방문하지 않은 곳에 대해 dfs로 탐색했다. dfs이기 때문에 인접 칸들을 다 탐색하고 다음 라인으로 넘어가기 때문에 이때 count를 1 증가시켜 준다.

dfs에서는 방문한 곳에 대해서는 true로 바꿔주고 방문하지 않은 곳이나 해당 칸의 높이가 강수량보다 높으면 dfs로 탐색해 주었다.

그 후 count가 최대인 값을 출력해 주었다.