백준 2468 - 안전 영역 (JAVA 자바)

백준 2468 - 안전 영역 (JAVA 자바)

 

 

 

기본적인 풀이방법은 유기농 배추(1012번: 유기농 배추 (acmicpc.net))와 크게 다르지 않지만,

차이점은 아래와 같습니다.

 

1) 물의 높이에 따라서 활성화되는 지역과 안되는 지역을 구분해주고

2) 그에 따라서 DFS 돌린 횟수를 모든 케이스에서 구한 뒤,

3) 그 중에서 가장 최댓값을 구한다. 

 

 

 

 

 

제가 풀이한 방법을 설명 드리겠습니다.

 

  - map[][] 배열을 통해서 주어진 안전 지대에 대한 값들을 받습니다.

  - visits[][] 배열로 dfs를 돌 때, 특정 지역을 방문했는지 안했는지에 대한 체크를 해줍니다.

  - copy_map[][]은 강수량에 따라서 잠기는 지역을 체크하기 위한 배열 정보입니다.

    map[][]을 바로 업데이트하면 안되는 이유가, 그 다음 강수량을 체크할 때 영향을 받기 때문입니다. 

    초기화 시키기 쉽게 하기 위해서 copy_map이라는 배열을 따로 선언해 줬습니다.

  - 특정 강수량 (예를 들면 8일 경우) 잠기는 지역은 -1로 대치(8이하의 숫자인 2~8의 숫자들)해줘서

    잠기는 지역인지를 쉽게 알 수 있도록 짜줬습니다.

  - 특정 강수량 체크가 끝난 후에는 다시 copy_map을 초기화 시켜 줍니다. (map 배열을 그대로 다시 복사해온다)

  - 아무 지역도 물에 잠기지 않을 수도 있기 때문에, 강수량은 0부터 체크를 하면서 돌아줍니다. 
    (모든 지역이 1로 되어 있을경우, 답은 1이 나와야한다)

    아래 반례를 참고하여 진행합니다.

 

입력:

5

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1 

 

답 : 1

 

 

 

 

 

 

import java.util.*;
 
public class safe_area {
 
    static int n, cnt;
    static int [][]map;
    static int [][]copy_map;
    static boolean [][]visits;
    static int dx[] = {-1,0,0,1};
    static int dy[] = {0,1,-1,0};
 
    public static void main(String args[]) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 5
 
        map = new int[n+1][n+1]; // 5*5
        copy_map = new int[n+1][n+1];
 
        int min = 101;
        int max = -1;
 
        for (int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                map[i][j] = sc.nextInt();
                min = Math.min(min, map[i][j]); // 2
                max = Math.max(max, map[i][j]); // 9
            }
        }
        int maxmax = -1;
        for(int i=0; i<=max; i++){
            cnt = 0;
            visits = new boolean[n+1][n+1];
            copy(); // map 초기화
 
            make_minus_one(i); // 침수되는 곳을 -1으로 만듦
 
 
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    if(!visits[j][k]){
                        dfs(j,k);
                        cnt++; // dfs를 한번 다 돌았으면 cnt를 1씩 증가시켜준다.
                    }
                }
            }
 
            maxmax = Math.max(maxmax, cnt);
 
        }
 
        System.out.print(maxmax);
 
    }
 
 
 
 
    public static void make_minus_one(int level){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if (copy_map[i][j]==level || copy_map[i][j]<level){
                    copy_map[i][j]=-1;
                    visits[i][j] = true;
                }
            }
        }
    }
 
    public static void copy(){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                copy_map[i][j] = map[i][j];
            }
        }
    }
 
    public static void dfs(int x, int y){
        visits[x][y] = true;
 
        for(int i=0; i<4; i++){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
 
            if (new_x<=0 || new_y<=0 || new_x>n || new_y>n){
                continue;
            }
 
            if(!visits[new_x][new_y] && map[new_x][new_y] !=-1){
                dfs(new_x, new_y);
            }
        }
    }
 
 
 
 
}