[Algorithm] 안전 영역 문제

Jong Min ·2025년 4월 3일

Algorithm

목록 보기

24/30

🏆 안전 영역 문제 (백준 2468)

📌 문제 설명

어떤 지역의 높이를 나타내는 N x N 크기의 2차원 배열이 주어진다. 이 지역은 비가 올 때 일정한 높이 이하의 지역이 물에 잠기고,
비의 양에 따라 물에 잠기지 않은 영역(안전한 영역)의 개수는 달라진다.

이때, 비의 양(침수 높이)이 다를 때마다 생기는 안전한 영역의 개수 중 최댓값을 구하자.

🎯 조건

1 ≤ N ≤ 100
지역의 높이는 1 이상 100 이하
비의 양이 0부터 최고 높이까지 변화할 때, 안전 영역 개수를 구한다.

💡 해결 방법

🔍 문제 접근

각 침수 높이(h)에 대해 안전한 영역을 찾아야 합니다
DFS를 사용해서 연결된 안전한 지역을 찾고 개수를 세는 방식을 사용합니다
높이가 h 이하인 곳은 물에 잠기므로 방문할 수 없습니다
최대 높이까지 모든 h에 대해 탐색한 후, 가장 많은 안전 영역을 가진 경우를 출력합니다

🚀 코드 구현 (DFS 활용)

import java.util.*;

public class SafeZone {
    static int N;
    static int[][] heightMap;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1}; // 상하좌우 이동
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        heightMap = new int[N][N];

        int maxHeight = 0; // 가장 높은 지역 찾기

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                heightMap[i][j] = sc.nextInt();
                maxHeight = Math.max(maxHeight, heightMap[i][j]); // 최고 높이 저장
            }
        }

        int maxSafeZones = 1; // 안전 영역 개수의 최댓값 (적어도 1개의 영역 존재)
        
        for (int h = 0; h <= maxHeight; h++) { // 각 침수 높이에 대해 탐색
            visited = new boolean[N][N];
            int safeZoneCount = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (heightMap[i][j] > h && !visited[i][j]) { // 물에 잠기지 않은 영역 탐색
                        dfs(i, j, h);
                        safeZoneCount++;
                    }
                }
            }
            maxSafeZones = Math.max(maxSafeZones, safeZoneCount); // 최대값 갱신
        }
        
        System.out.println(maxSafeZones);
    }

    static void dfs(int x, int y, int h) {
        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 (heightMap[nx][ny] > h && !visited[nx][ny]) { 
                    dfs(nx, ny, h);
                }
            }
        }
    }
}