백준 - 2468번(안전 영역)

문제 출처: https://www.acmicpc.net/problem/2468

문제

• 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

• 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

  	6	8	2	6	2
  	3	2	3	4	6
  	6	7	3	3	2
  	7	2	5	3	6
  	8	9	5	2	7

• 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

  	6	8	2	6	2
  	3	2	3	4	6
  	6	7	3	3	2
  	7	2	5	3	6
  	8	9	5	2	7

• 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

• 또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

  	6	8	2	6	2
  	3	2	3	4	6
  	6	7	3	3	2
  	7	2	5	3	6
  	8	9	5	2	7

• 이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

• 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

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

public class Main {

    private static int[][] directions = {
            { -1, 0  }, // 상
            {  1, 0  }, // 하
            {  0, -1 }, // 좌
            {  0, 1  }, // 우
    };

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 행, 열의 수
        int[][] matrix = new int[N][N];
        int maxValue = 0;
        // 배열 생성
        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(tokenizer.nextToken());
                maxValue = Math.max(maxValue, matrix[i][j]);
            }
        }

        int max = 1;

        for (int k = 1; k < maxValue; k++) {
            int temp = 0;
            boolean[][] flag = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (matrix[i][j] > k && !flag[i][j]) {
                        temp++;
                        flag[i][j] = true;
                        dfs(k, i, j, N, matrix, flag);
                    }
                }
            }
            max = Math.max(max, temp);
        }

        System.out.println(max);
    }

    private static void dfs(int height, int row, int col, int N, int[][] matrix, boolean[][] flag) {
        for (int i = 0; i < 4; i++) {
            int dy = row + directions[i][0];
            int dx = col + directions[i][1];

            // 가능한 인덱스이고
            if (dy >= 0 && dy < N && dx >= 0 && dx < N) {
                // 물에 잠기지 않은 곳이면
                if (matrix[dy][dx] > height && !flag[dy][dx]) {
                    flag[dy][dx] = true;
                    dfs(height, dy, dx, N, matrix, flag);
                }
            }
        }
    }

}

• DFS를 이용하여 해결하였다.
• 들어온 값 중에서 가장 큰 값을 찾아 그 값까지 반복을 진행하도록 하였다.
• 강수량을 0부터 두고 반복하여 가장 땅이 많이 나오는 경우를 찾도록 진행하였다. 이때, 강수량이 0일때 땅의 갯수가 1인 것을 간과하여 이해하는데 시간이 조금 걸렸다.