[Java] 백준 안전 영역

1. 문제분석

 

비가 올 때 안전지역, 즉 비의 높이 이하인 지역의 영역의 개수를 구하는 문제다.

나는 문제가 도대체 뭘 구하라는 건지 몰라서 구글링을 했다. 막상보니 영역을 1개로 치고 그 영역을 구하는 것이다.

 

1번째 그림을 보자. 비의 높이는 4이므로 4 이하는 전부 회색으로 처리한다.

그 후, 나머지 영역을 보면 (6,8), (6), (7,6,7,8,9,5,5), (6,7), (6)으로 5개 나온다.

 

2번째 그림은 비의 높이가 6일 때의 상태다. 6이하는 전부 회색으로 처리한 상태고 나머지 영역을 구하면 된다.

(8), (7), (7,8,9), (7) 총 4개의 영역이 나온다. 

 

우리는 이 영역의 최대값을 구하면 되는 것이다.

기초적인 DFS에서 조건 1가지를 주면 구할 수 있다.

 

먼저 비의 높이는 1 ~ 100이라고 한다. 이 것을 다 구하는 것 보다 배열의 값을 기준으로 보는 것이 더 좋다.

위의 예시로 해당 배열의 최댓값은 9, 최솟값은 2가 된다.

만약 비의 높이가 1일 때는 전부다 안잠기게 된다. 높이가 2부터이므로 비의 높이 2일때부터 시작하면 된다.

만약 비의 높이ㅏ 10이라고 하자. 최대값이 9이므로 전부다 잠기게 된다. 비의 높이 9일때 까지 증가하면 된다.

 

주의할 점은 한번에 잠기는 것이다.

배열의 모든 값이 9라고 하자. 그렇다면 비의 높이 10이기 전에는 영역이 1로 된다.

10이면 바로 0이되므로 1을 출력해줘야 한다.

2. 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] arr;
    static int size;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        size = Integer.parseInt(br.readLine());
        int max = 0, min = Integer.MAX_VALUE;
        arr = new int[size][size];
        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                int input = Integer.parseInt(st.nextToken());
                max = Math.max(max, input);
                min = Math.min(min, input);
                arr[i][j] = input;
            }
        }

        int maxArea = 0;
        int area = 0;
        for (int i = min; i <= max; i++) {
            //visited 넣어주기 -> 물 높이 이하면 방문한 것으로 취급
            visited = new boolean[size][size];
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    if (arr[j][k] <= i) {
                        visited[j][k] = true;
                    }
                }
            }
            //방문한 것을 기준으로 dfs 시작
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    if (!visited[j][k]) {
                        area++;
                        dfs(j, k);
                    }
                }
            }
            maxArea = Math.max(maxArea, area);
            area = 0;
        }
        //모든 지역이 안차다가 한번에 찰 수도 있음.
        if(maxArea == 0){
            //1을 추가
            maxArea = 1;
        }
        System.out.println(maxArea);
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int moveX = x + dx[i];
            int moveY = y + dy[i];

            if (check(moveX, moveY)) {
                dfs(moveX, moveY);
            }
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || x >= size) return false;
        if (y < 0 || y >= size) return false;
        return !visited[x][y];
    }
}

최소 섬의 높이 ~ 최대 섬의 높이까지 for문을 돌렸다.

만약 비의 높이 이하인 곳은 visited배열 값을 true로 하여 방문했다고 처리했다.

dfs를 최초 실행할 때가 영역을 구하는 것 이므로 area를 1 더해주면 된다.

3. 마무리

한국어를 못알아 먹은 문제다.. DFS는 금방 구현했지만 뭘 출력하라는지 몰라서 검색해본 문제..