[백준] 2468번 : 안정 영역 (JAVA)

인간몽쉘김통통·2023년 11월 26일

그래프 탐색 백준 알고리즘

백준

목록 보기

27/92

문제

이해

2차원 배열 공간은 건물의 높이를 의미한다. 장마철에 비가 잠기지 않는 영역의 최대 개수를 계산해야 한다.

비에 잠기는 기준은 건물의 높이가 비의 높이 이하인 경우이다.

위 경우는 비의 높이가 4인 경우이다. 안전 영역은 상,하,좌,우 공간이 연속된 모든 영역을 1개로 취급한다. 꼭짓점끼리만 붙어있는 경우는 인접하지 않은 것으로 취급한다.

따라서, 예시의 경우 안전 영역은 총 5개이다.

생길 수 있는 안전 영역의 최대 개수를 계산하면 된다.

단, 건물의 높이는 1부터 100까지이고 물의 높이는 0부터 시작한다.

접근

BFS를 통한 접근 가능한 영역의 총 개수를 세면 될 것 같다.

물의 높이에 따라서 영역의 개수가 달라지기 때문에 물의 높이의 경우를 모두 조사하면 된다.

물의 높이는 0부터 최대 건물의 높이까지 조사하면 된다.

영역의 개수를 셀 때는 boolean 2차원 배열 safe를 두었다. safe는 물의 높이보다 건물의 높이가 커서 안전한 건물의 정보를 담고 있다. true인 경우 안전하다.

각 높이에 따라 safe를 정의하고 (0,0)부터 탐색하여 true인 경우 bfs를 수행한다.

bfs를 통해 인접 영역을 확인하고 방문한 영역은 다음 탐색때 중복되지 않기 위해 false로 초기화한다.

한 케이스의 2차원 탐색이 끝나면 영역의 개수가 계산된다.

이후로 최대값을 찾기 위해 비교 후 갱신하면 된다.

코드

package java_baekjoon;

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

public class prob2468 {
    static int N;
    static int[][] square;
    static int max = Integer.MIN_VALUE;
    static int ans;
    static int[] d_row = { -1, 0, 1, 0 };
    static int[] d_col = { 0, -1, 0, 1 };

    static class xy {
        int x;
        int y;

        public xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

        N = Integer.parseInt(br.readLine());
        square = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                square[i][j] = Integer.parseInt(st.nextToken());

                if (max < square[i][j]) {
                    max = square[i][j];
                }
            }
        }

        for (int height = 0; height < max; height++) {
            boolean[][] safe = new boolean[N][N];
            Queue<xy> q = new LinkedList<>();
            int cnt = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (square[i][j] > height) {
                        safe[i][j] = true;
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (safe[i][j]) {
                        q.add(new xy(i, j));
                        safe[i][j] = false;

                        cnt++;

                        while (!q.isEmpty()) {
                            xy coordinate = q.poll();

                            for (int k = 0; k < 4; k++) {
                                int new_x = coordinate.x + d_row[k];
                                int new_y = coordinate.y + d_col[k];

                                if (new_x >= 0 && new_x < N && new_y >= 0 && new_y < N && safe[new_x][new_y]) {
                                    q.add(new xy(new_x, new_y));
                                    safe[new_x][new_y] = false;
                                }
                            }
                        }
                    }
                }
            }

            if (ans < cnt) {
                ans = cnt;
            }
        }

        System.out.println(ans);
    }
}