[BOJ] 백준 2468번: 안전 영역(Java)

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

문제

 

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

 

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

 

난이도

실버 1

 

Sol

아무 지역도 물에 잠기지 않을 수 있다는 조건이 있기 때문에 이를 고려하여 answer의 초기값을 1로 줘야 한다. 로직에서 걸러낼 수 있을 줄 알고 answer의 초기값을 0으로 줬었는데 안되네.. N과 상관 없이 배열의 모든 요소를 1로 입력했을 때의 결과로 확인할 수 있다.

public class B2468_안전영역 {
    static int[][] field;
    static boolean[][] isvisited;
    static int N;
    static int answer = 1;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

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

        field = new int[N][N];

        int max = 0;

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

            for(int j=0; j<N; j++){
                field[i][j] = Integer.parseInt(token.nextToken());
                max = Integer.max(field[i][j], max);
            }
        }
        // input

        for(int i=1; i<max; i++){
            isvisited = new boolean[N][N];
            int count = 0;
            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    if(field[j][k]<=i) isvisited[j][k] = true;
                    // 물에 잠기는 영역을 방문 처리해 탐색 시 방문하지 못하게 한다
                }
            }

            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    if(!isvisited[j][k]){
                        count++;
                        isvisited[j][k] = true;
                        search(j, k);
                    }
                }
            }

            answer = Integer.max(answer, count);
//            System.out.println(i + "까지 물에 잠길 때, 영역의 최대 개수 " + count);
        }
        // operation

        System.out.println(answer);
        // output
    }

    static void search(int x, int y){
        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(!isvisited[nx][ny]){
                isvisited[nx][ny] = true;
                search(nx, ny);
            }
        }
    }
}