안전 영역 - 2468

문제

입력
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

출력
5

풀이

package Baekjoon;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 안전 영역 - 2468 - s1
public class ex2468 {
    static int[] dx={0,1,0,-1};
    static int[] dy={-1,0,1,0};
    static int n,cnt=0;
    static int[][] arr;
    static int max=Integer.MIN_VALUE;
    static int[][] ch;
    static ArrayList<Integer> list;
    public static void DFS(int x,int y,int h){
        ch[x][y]=1;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<n){
                if(arr[nx][ny]>h && ch[nx][ny]==0){
                    DFS(nx,ny,h);
                }
            }
        }
    }

    public static void solution(int[][] arr,int[][] ch, int h){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j]>h && ch[i][j]==0){
                    DFS(i,j,h);
                    cnt++;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);

        n=sc.nextInt();
        arr = new int[n][n];
        ch = new int[n][n];
        list = new ArrayList<>();
        list.add(1);

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                arr[i][j] = sc.nextInt();
                max = Math.max(max,arr[i][j]);
            }
        }

        //각 i 높이의 영역의 수를 구해야함.
        for(int i=1; i<max; i++){
            cnt=0;
            solution(arr,ch,i); //arr탐색
            list.add(cnt);
            ch = new int[n][n]; //체크배열 초기화
        }
        Collections.sort(list);
        System.out.println(list.get(list.size()-1));
    }
}

일단, 결론부터 얘기 하자면 max변수를 이용해 최고높이를 구하는 과정에서 max=0으로 선언했더니 런타임 에러가 떳다. 최댓값을 구할 땐 INTEGER.MIN_VALUE로 선언하자.

1. 각 높이 별로 solution을 돌려줘야한다.여기서 solution()은 높이 h 보다 높고 방문하지 않은 곳을 방문한다.침수되지 않은 곳의 영역을 파악한다. DFS()호출
2. DFS()가 호출되면 범위 내에서 if문을 걸고 다음 좌표를 DFS()재귀호출한다. 그러고 체크배열에 체크!!

어렵게 생각하지 말자.