[백준] 2468번 - 안전 영역 (Silver 1)

문제 링크

백준 2468번 - 안전 영역 (Silver 1)

문제 설명

위에서 내려다보면 N x N 정사각형 모양인 지역이 있다.
이 지역의 높이 정보는 N x N 크기의 2차원 배열로 주어진다.
각 칸에 쓰여있는 높이가 해당 지점의 높이에 대응된다.

이 지역에 비가 내려서 특정 높이 이하의 지역이 모두 물에 잠겼다.
내린 비의 양에 따라 물에 잠기지 않은 안전 영역의 개수가 달라지는데, 가능한 안전 영역의 개수의 최댓값을 구하시오.
물에 잠기지 않은 두 지점이 같은 영역에 있다는 것은 한 지점에서 출발하여 물에 잠기지 않은 지점들을 따라 상하좌우로만 이동해서 다른 지점으로 갈 수 있다는 것을 의미한다.

정답 코드 및 설명

비가 오는 양에 따라 안전한 영역의 개수를 구해주면 된다.
비가 아예 오지 않는 경우는 모든 지역이 안전하므로, 안전 영역의 개수는 1이다.
높이가 가장 낮은 지역의 높이를 min, 높이가 가장 높은 지역의 높이를 max라고 하자.
이제 비가 오는 양이 min 이상 max 미만일 때에 대해서 안전 영역의 개수를 구해주면 된다.

안전 영역의 개수는 BFS를 통해 구할 수 있다.
보다 구체적으로 말하면, 모든 지점을 순회하면서 1 ~ 3을 반복한다.

1. 물에 잠긴 지점이라면 건너뛴다.
2. 현재 지점은 물에 잠기지 않았다. 이미 방문하지 않은 지점이라면, BFS를 수행한다.
3. BFS를 수행하면서 방문한 지점은 모두 방문처리를 해준다.

BFS가 수행된 총 회수가 안전 영역의 개수가 된다.

노드가 M개인 그래프에서 BFS를 수행했을 때 시간 복잡도는 $O(M)$이다.
따라서, 각 높이에 대해 안전 영역의 개수를 구하는 과정의 시간 복잡도는 $O(N^2)$이다.
이는 BFS의 시간 복잡도는 선형이고, 전체 칸 수는 $N^2$이기 때문이다.
N이 100 이하이므로 각 높이에 대해 안전 영역의 개수를 구하는 과정은 대략 1만번의 연산이면 충분함을 알 수 있다. 높이는 1 이상 100 이하의 정수이므로, 가능한 높이는 최대 100가지이고 따라서 대략 100만번의 연산이면 충분하다. 제한 시간은 1초이므로 넉넉하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2468 {
    int n, min, max;
    int[][] height;
    boolean[][] isChecked;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        min = Integer.MAX_VALUE;
        max = 0;
        height = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                height[i][j] = Integer.parseInt(st.nextToken());
                if (height[i][j] < min) min = height[i][j];
                if (height[i][j] > max) max = height[i][j];
            }
        }
    }

    int numOfAreas(int rain) {
        isChecked = new boolean[n][n];
        int area = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isChecked[i][j]) continue;
                if (height[i][j] <= rain) continue;
                setArea(i, j, rain);
                area++;
            }
        }
        return area;
    }

    void setArea(int i, int j, int rain) {
        final int[][] NEXT = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        if (height[i][j] <= rain) return;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        isChecked[i][j] = true;
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int k = 0; k < 4; k++) {
                int currI = curr[0] + NEXT[k][0];
                int currJ = curr[1] + NEXT[k][1];
                if (!isValid(currI, currJ)) continue;
                if (isChecked[currI][currJ]) continue;
                isChecked[currI][currJ] = true;
                if (height[currI][currJ] <= rain) continue;
                queue.add(new int[]{currI, currJ});
            }
        }
    }

    boolean isValid(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < n;
    }

    void solution() throws IOException {
        input();
        int maxOfAreas = 1; // 비가 아예 안 온 경우
        for (int i = min; i < max; i++) {
            maxOfAreas = Math.max(maxOfAreas, numOfAreas(i));
        }
        System.out.println(maxOfAreas);
    }

    public static void main(String[] args) throws IOException {
        new BOJ2468().solution();
    }
}