[알고리즘] 백준 2468 - 안전 영역

1. 문제

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

2. 입력

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

3. 풀이

섬의 개수(4963)와 거의 비슷한 풀이방법으로 해결했다.

• 주의점
  - '지역'의 높이가 1~100 사이이며
  - '수면'의 높이는 0~100 사이이다.

전체 지형을 dfs로 돌면서 모든 높이에 대해 안전구역 개수를 검사한다.

4. 코드

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

public class safeGround_2468 {

    static int n;
    static int[][] map;
    static boolean[][] visit;

    static int xdir[] = {1,-1,0,0};
    static int ydir[] = {0,0,1,-1};

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(bf.readLine());

        map = new int[n][n];
        visit = new boolean[n][n];

        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            for(int j=0;j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        int answer[] = new int[101];

        //0~100사이 높이의 수면에 대해 검사
        for(int i=0;i<=100;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if(!visit[j][k]&&map[j][k]>i){
                        visit[j][k] = true;
                        dfs(i,j,k);
                        //dfs를 한번 돌고 나올떄 마다 연결된 안전구역이 1개 있는 것
                        answer[i]= ++count;
                    }
                }
            }
            for(boolean a[]:visit){
                Arrays.fill(a,false);
            }
            count = 0;
        }



        Arrays.sort(answer);

        System.out.println(answer[100]);


    }

    //dfs로 연결된 안전구역 탐색
    public static void dfs(int height,int i, int j){

        for(int k=0;k<4;k++){
            int x = i+xdir[k];
            int y = j+ydir[k];

            if(x<n && y<n && x>=0 && y>=0){
                if(map[x][y]>height && !visit[x][y]){
                    visit[x][y] = true;
                    dfs(height,x,y);
                }
            }
        }

    }
}