백준 No.2468 안전 영역- JAVA

문제

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

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

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

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

 

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

풀이

int map[][] 배열에 주어진 값들을 모두 받는데 받으면서 높이가 가장 높은 곳을 찾아야 한다. 그래야 가장 높은 곳까지 잠겼을 때의 상황을 비교하여 최댓값을 구할 수 있기 때문이다. 그렇게 받은 값으로 탐색을 시도하는데 BFS, DFS둘 다 가능하고 나는 DFS로 했다. 

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

public class Main {

    static int map[][];
    static boolean visitied[][];

    static int N;

    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};

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

        map = new int[N][N];
        StringTokenizer st;
        int max = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(map[i][j],max);
            }
        }
        int tempMax = 0;
        for (int height = 0; height <= max; height++) {
            visitied = new boolean[N][N];
            int count = 0;
            for (int i = 0; i < N ; i++) {
                for (int j = 0; j < N; j++) {
                    if(!visitied[i][j] && map[i][j] > height ){
                        count += dfs(i,j,height);
                    }
                }
            }
            tempMax = Math.max(tempMax,count);
        }
        System.out.println(tempMax);
    }

    static int dfs(int x,int y,int height){
        visitied[x][y] = true;

        for (int i = 0; i < 4 ; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(visitied[nx][ny]) continue;
            if (map[nx][ny] > height) dfs(nx,ny,height);
        }
        return 1;

    }
}