[백준] 2468번: 안전 영역 (Java)

1. 문제 설명

지역이 N*N(2차원 배열)으로 이루어져 있고, 각 지역의 깊이 정보가 제공된다.

안전한 영역:

• 물에 잠기지 않는 지점들이 위,아래, 오른쪽 or 왼쪽으로 인접하고
• 그 크기가 최대인 영역

지역의 높이 정보가 주어졌을 때, 물에 잠기지 않는 안전한 영역의 최대 개수를 구한다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 비의 양
  • 입력으로 주어진 지역 높이 정보를 N * N 배열(region)에서 넣으면서
  • 모든 지역 높이를 Set에 저장한다. (rain)
  • Set의 값들이 탐색할 비의 양
• 비의 양에 대한 안전 영역 개수 계산
  • rain에 있는 비의 양을 하나씩 꺼내 아래 과정을 반복한다.
  • visited 배열 초기화: 현재 비의 양에 대한 탐색을 위해 N * N 크기 배열을 초기화
  • region의 모든 지역 탐색한다.
  • 만약 현재 지역의 높이가 비의 양보다 높고, 아직 방문하지 않았다면
    • 안전 영역 개수를 1 증가시킨다.
    • 이 지역을 시작점으로 DFS를 호출하여 이어진 안전 지역을 방문 처리한다.
• DFS
  • 시작 위치(x, y)를 인자로 받는다.
  • 상하좌우 방향으로 이동(방향배열 사용)하며, 아래 조건을 만족하는 인접 지역(nx, ny)를 탐색한다.
    • 배열의 유효 범위에 있음
    • 현재 비의 양에 잠기지 않음
    • 아직 방문하지 않음
  • 재귀적으로 DFS를 호출하여 탐색한다.
• 최댓값 갱신: 각 비의 양에 대해 계산된 안전 영역 중 최댓값을 구한다.

 

3. 최종 코드

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

public class Main{
    static int n; // 지역 행렬 크기
    static int[][] region; // 지역 정보 - 높이 저장
    static boolean[][] visited; // 방문 여부 확인
    static Set<Integer> rain; // 내릴 수 있는 비의 양
    static int maxCount;
    
    static int[] moveX = {-1, 1, 0, 0}; // 왼쪽, 오른쪽
    static int[] moveY = {0, 0, -1, 1}; // 위, 아래

    static void dfs(int x, int y, int rain) {
        visited[x][y] = true; // 방문 처리

        for (int i=0; i<4; i++) { // 방향 배열 사용 (현재 위치의 상하좌우를 탐색)
            int nx = moveX[i] + x;
            int ny = moveY[i] + y;
            if (nx>=0 && nx<n && ny>=0 && ny<n // 해당 위치가 유효하고
                    && region[nx][ny] > rain && !visited[nx][ny]) { // 잠기지 않고, 아직 방문하지 않은 경우
                dfs(nx, ny, rain); // 재귀
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 초기화
        n = Integer.parseInt(br.readLine());
        region = new int[n][n];
        visited = new boolean[n][n]; // 방문 여부 초기화
        rain = new HashSet<>();
        rain.add(0); // 아무 지역도 물에 잠기지 않을 수 있음
        maxCount = 0;

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                region[i][j] = Integer.parseInt(s[j]); // 지역 높이 정보 저장
                rain.add(region[i][j]); // 내릴 수 있는 비의 양 저장 (중복 방지)
            }
        }

        List<Integer> rain_list = new ArrayList<>(rain); // Set -> List로 변환
        // 내리는 비의 양에 따라 DFS로 안전 영역 구하기
        for (int i = 0; i < rain_list.size(); i++) {
            int count = 0; // 비의 양에 따른 안전 영역 개수
            int rain = rain_list.get(i); // 비의 양
            visited = new boolean[n][n]; // 방문 여부 배열 초기화
            for (int j = 0; j < n; j++) { // 모든 지역 탐색
                for (int k = 0; k < n; k++) {
                    if (region[j][k] > rain && !visited[j][k]) {
                        // 현재 지역의 높이가 비의 양보다 높고, 아직 방문하지 않았다면
                        count++; // 안전 영역 개수 증가
                        dfs(j, k, rain); // DFS 호출
                    }
                }
            }

            // 최대 개수 갱신
            if (count > maxCount) maxCount = count;
        }

        System.out.println(maxCount);
    }
}