백준 자바 :: 안전영역(DFS)

높이가 1부터 100이라고 해서 처음에 1~100을 다 탐색하려고 했는데

maxHeight를 구하는 것으로 변경했고

1부터 탐색하면 틀리고 0부터 탐색해야 한다!

 

그리고 visited와 count 초기화에 주의 필요!

 

 

 

 

 

 

 

import java.util.*;

import java.io.*;

public class Main{

    static int N;

    static int[][] array;

    static boolean[][] visited;

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

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        array = new int[N][N];

        for(int i = 0; i < N; i++){

            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < N; j++){

                array[i][j] = Integer.parseInt(st.nextToken());

            }

        }

        // 주의! maxHeight 값을 구하자!

        int maxHeight = 0;

        for(int i = 0; i < N; i++){

            for(int j = 0; j < N; j++){

                maxHeight = Math.max(array[i][j], maxHeight);

            }

        }

        int maxValue = 0;

        for(int height = 0; height <=maxHeight; height++){ // 높이를 0부터 시작해야함!!

            visited = new boolean[N][N]; // 초기화 주의!

            int count = 0;

            for(int i = 0; i < N; i++){

                for(int j = 0; j < N; j++){

                    if(!visited[i][j] && array[i][j] > height){

                        count++;

                        DFS(i, j, height);

                    }

                }

            }

            maxValue = Math.max(maxValue, count);

        }

       

        System.out.println(maxValue);

    }

    static void DFS(int x, int y, int height){

        visited[x][y] = true;

        for(int i = 0; i < 4; i++){

            int now_x = x + dx[i];

            int now_y = y + dy[i];

            if(now_x >=0 && now_y >=0 && now_x < N && now_y < N && !visited[now_x][now_y] && array[now_x][now_y] > height){

                DFS(now_x, now_y, height);

            }

        }

    }

}