[알고리즘 문제 풀이] 백준 2468 안전영역 (BFS/DFS)

 

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

import java.util.StringTokenizer;
import java.util.Scanner;


public class Main{

    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static int safeArea;

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

    static int maxHeight;
    static int ans;

    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());

        arr=new int[N][N];

        maxHeight=0;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                int k = Integer.parseInt(st.nextToken());
                arr[i][j]=k;
                if(maxHeight <k){
                    maxHeight = k;
                }
            }
        }

        safeArea=0;
        ans=0;

        for(int h=0;h<=maxHeight;h++){
            visited=new boolean[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(arr[i][j] > h && !visited[i][j]) {
                        dfs(i, j, h);
                        safeArea++;
                    }
                }
            }
            if(ans < safeArea) ans=safeArea;
            safeArea=0;

        }

        System.out.println(ans);

    }

    static void dfs(int x,int y,int h){
        visited[x][y]=true;

        for(int i=0;i<4;i++){
            int movedX = dx[i]+x;
            int movedY = dy[i]+y;

            if(movedX <0 || movedY<0 || movedX>=N || movedY>=N) continue;
            if(visited[movedX][movedY]) continue;
            if(arr[movedX][movedY] <= h) continue;
            dfs(movedX,movedY,h);

        }
    }

}