[BOJ] 2468 - 안전 영역(Java)

📔문제

https://leetcode.com/problems/find-peak-element/description/

🔍 접근법

이 문제는 비의 양에 따라 물의 높이가 달라질 때, 물에 잠기지 않는 '안전 영역'의 최대 개수를 구하는 문제입니다. 여기서 '안전 영역'이란, 물에 잠기지 않은 육지들이 상하좌우로 붙어있는 덩어리를 의미합니다.

문제를 처음 봤을 때, 다음과 같은 단계로 해결 전략을 세웠습니다.

1. 물의 높이 시뮬레이션: 비가 아예 오지 않은 상황부터, 가장 높은 지역이 잠길 때까지 모든 경우를 확인해야 합니다. 따라서, 물의 높이를 0부터 맵의 최대 높이까지 1씩 증가시키는 반복문이 필요합니다.
2. 영역 개수 계산: 특정 물의 높이가 정해졌을 때, 물에 잠기지 않는 육지 덩어리가 몇 개인지 세어야 합니다.
3. 최대값 갱신: 각 높이마다 계산된 안전 영역의 개수를 이전에 기록된 최대 개수와 비교하여, 더 큰 값으로 계속 업데이트합니다.

💻 코드

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

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int max = Integer.MIN_VALUE;
    static int safeRegionCnt = 1; //아무 지역도 물에 안잠기는 경우 고려(하나의 영역이 됨)
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int N;

    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+1][N+1];

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                int heightInfo = Integer.parseInt(st.nextToken()); //높이 정보
                if(heightInfo > max) max = heightInfo; //최댓값 갱신
                graph[i][j] = heightInfo;
            }
        }

        for(int z=1; z<=max; z++){
            visited = new boolean[N+1][N+1];
            int tmpRegionCnt = 0;

            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(!visited[i][j] && graph[i][j] > z){
                        tmpRegionCnt++;
                        dfs(i, j, z);
                    }
                }
            }

            if(tmpRegionCnt > safeRegionCnt) safeRegionCnt = tmpRegionCnt;
        }

        System.out.println(safeRegionCnt);
    }

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

        for(int i=0; i<=3; i++){
            int newX = x+dx[i];
            int newY = y+dy[i];

            if(rangeCheck(newX, newY) && !visited[newX][newY] && graph[newX][newY] > z){
                dfs(newX, newY, z);
            }
        }
    }

    static boolean rangeCheck(int x, int y){
        return x>=0 && y>=0 && x<N && y<N;
    }
}

💡 마무리

단순 DFS/BFS 문제(실버 2~3)와 비교했을 때, 이번 실버 1 문제는 '물의 높이'라는 탐색의 기준을 바꿔가며 반복적으로 DFS를 수행해야 하는 조건이 추가되었다고 느꼈습니다.

앞으로 비슷한 문제를 만나면, 단순히 한 번의 탐색으로 끝낼 것이 아니라 "무엇을 기준으로, 어떻게 반복 탐색을 수행해야 하는가?" 를 먼저 고민하는 습관을 들여야겠습니다.