2468번: 안전 영역

문제

어떤 지역의 높이 정보가 N×N 크기의 2차원 배열로 주어집니다. 많은 비가 내리면 수위 이하의 모든 지점이 물에 잠기게 됩니다. 물에 잠기지 않는 안전한 영역이란, 물에 잠기지 않은 지점들이 상하좌우로 인접해 있으며 그 크기가 최대인 영역(덩어리)을 말합니다. 비의 양(수위)에 따라 물에 잠기는 지점이 달라질 때, 발생할 수 있는 안전한 영역의 최대 개수를 구하는 문제입니다.

• 입력: 첫째 줄에 2차원 배열의 행과 열의 개수 N이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 각 지점의 높이가 주어집니다. (높이는 1 이상 100 이하의 정수)
• 출력: 첫째 줄에 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력합니다.

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

풀이

비가 얼마나 올지 알 수 없으므로, 비가 전혀 오지 않는 경우(수위 0)부터 해당 지역의 최고 높이까지 모든 수위의 경우의 수를 시뮬레이션하여 안전 영역의 개수를 구해야 하는 그래프 탐색 + 브루트포스 문제입니다.

1. 입력 및 최고 높이 탐색: N x N 배열에 높이 정보를 입력받으면서, 강수량 탐색의 상한선을 정하기 위해 가장 높은 지점의 높이(maxH)를 기록해 둡니다.
2. 수위별 시뮬레이션: 수위 h를 0부터 maxH까지 1씩 증가시키며 반복문을 수행합니다. (주의: 아무 지역도 물에 잠기지 않을 수 있으므로 수위는 반드시 0부터 시작해야 합니다.)
3. 안전 영역 탐색 (DFS): 각 수위 h마다 방문 배열(visited)을 새롭게 초기화하고 맵 전체를 2중 for문으로 순회합니다. 현재 지점의 높이가 수위 h보다 높고(a[i][j] > h), 아직 방문하지 않았다면(!visited[i][j]) 새로운 안전 영역 덩어리를 발견한 것이므로 덩어리 개수(cnt)를 1 증가시키고 해당 위치부터 깊이 우선 탐색(DFS)을 시작하여 인접한 안전 지대를 모두 방문 처리합니다.
4. 최댓값 갱신: 각 수위 h에 대한 탐색이 끝날 때마다, 구해진 안전 영역의 개수(cnt)와 기존 최댓값(ans)을 비교하여 가장 큰 값으로 갱신합니다.

코드

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

public class Main {
    static int n;
    static int[][] a;
    static boolean[][] visited;
    
    // 상하좌우 탐색을 위한 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

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

       n = Integer.parseInt(br.readLine());
       a = new int[n][n];
       int maxH = 0;
       
       // 지역의 높이 정보 입력 및 최고 높이 파악
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             a[i][j] = Integer.parseInt(st.nextToken());
             maxH = Math.max(a[i][j], maxH);
          }
       }

       int ans = 0;
       
       // 수위(h)를 0부터 최고 높이까지 높여가며 완전 탐색
       for (int h = 0; h <= maxH; h++) {
          visited = new boolean[n][n]; // 수위가 바뀔 때마다 방문 배열 초기화
          int cnt = 0;
          
          for (int i = 0; i < n; i++) {
             for (int j = 0; j < n; j++) {
                // 현재 수위 h보다 높아서 잠기지 않았고, 아직 방문하지 않은 지점
                if (a[i][j] > h && !visited[i][j]) {
                   dfs(i, j, h);
                   cnt++; // 안전 영역 덩어리 개수 증가
                }
             }
          }

          // 해당 수위에서의 안전 영역 개수와 기존 최댓값 비교
          ans = Math.max(ans, cnt);
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }

    // 연결된 안전 영역을 방문 처리하는 DFS 메서드
    static void dfs(int y, int x, int h) {
       visited[y][x] = true;

       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          // 맵 범위를 벗어나면 무시
          if (ny < 0 || nx < 0 || ny >= n || nx >= n)
             continue;
             
          // 현재 수위 h 이하이거나(물에 잠김) 이미 방문한 곳이면 무시
          if (a[ny][nx] <= h || visited[ny][nx])
             continue;
             
          // 연결된 안전 구역으로 계속 탐색
          dfs(ny, nx, h);
       }
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS), 브루트포스 알고리즘 (Brute Force)