[백준/DFS] 2468번 안전 영역 (JAVA)

문제

---

풀이

DP만 주구장창 풀었더니 다른 유형들 감이 떨어지는 것 같아서 DFS/BFS 문제도 같이 꾸준히 풀려고 한다.

오늘 푼 문제는, 조건에 맞춰 배열에서 영역을 최대 몇 개 만들 수 있는지 찾는 전형적인 DFS/BFS 문제였다. 나는 DFS로 풀이했다.

1. countMaxSafeArea()
   • limit을 0부터 maxHeight까지 변화시키며
   • 그 때마다 safeAreaOnLimit을 구하고
   • maxSafeAreaCount를 최댓값으로 갱신한다.

2. countSafeAreaOnLimit(limit)
   • 주어진 limit을 조건으로 heights를 탐색하고 currentSafeAreaCount를 구한다.
   • 아직 방문하지 않았고 물에 잠기지 않는 경우에 dfs()를 재귀 호출하여
   • 방문한 영역을 모두 visited 표시한다.
   • 하나의 영역의 탐색이 끝날 때마다 curretSafeAreaCount를 증가시킨다.

3. dfs(limit, y, x)
   • (y,x)의 상하좌우를 탐색하며 조건에 맞는 경우 dfs()를 재귀 호출한다.

코드

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

public class Main {

    private static final int MAX_SIZE = 100;
    private static final int MIN_HEIGHT = 1;
    private static final int MIN_LIMIT = 0;
    private static final int[] dy = {1, -1, 0, 0};
    private static final int[] dx = {0, 0, 1, -1};

    private static int n;
    private static int[][] heights = new int[MAX_SIZE][MAX_SIZE];
    private static boolean[][] visited = new boolean[MAX_SIZE][MAX_SIZE];

    private static int maxHeight = MIN_HEIGHT;
    private static int currentSafeAreaCount;
    private static int maxSafeAreaCount;

    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());
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                heights[i][j] = Integer.parseInt(line[j]);
                maxHeight = Math.max(heights[i][j], maxHeight);
            }
        }
        countMaxSafeArea();
        bw.append(String.valueOf(maxSafeAreaCount));

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

    private static void countMaxSafeArea() {
        for (int i = maxHeight; i >= MIN_LIMIT; i--) {
            visited = new boolean[MAX_SIZE][MAX_SIZE];
            for (boolean[] row : visited) Arrays.fill(row, false);
            currentSafeAreaCount = 0;
            countSafeAreaOnLimit(i);
            maxSafeAreaCount = Math.max(maxSafeAreaCount, currentSafeAreaCount);
        }
    }

    private static void countSafeAreaOnLimit(int limit) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && heights[i][j] > limit) {
                    dfs(limit, i, j);
                    currentSafeAreaCount++;
                }
                visited[i][j] = true;
            }
        }
    }

    private static void dfs(int limit, int y, int x) {
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (isInBound(ny, nx) && !visited[ny][nx]) {
                visited[ny][nx] = true;
                if (heights[ny][nx] > limit)
                    dfs(limit, ny, nx);
            }
        }
    }

    private static boolean isInBound(int ny, int nx) {
        return ny >= 0 && ny < n && nx >= 0 && nx < n;
    }
}