[백준 2468] 안전 영역

 

 

인접노드 탐색 문제이다.

 

높이 정보를 조건으로 주어야 한다는 것만 추가해서 풀면된다.

 

이처럼 높이 조건을 돌려보면서 컴포넌트 개수 중 최고 값을 찾으면 된다.

 

visited 배열을 반복적으로 초기화하면서 DFS(높이 조건) 와 컴포넌트 세는 DFS 를 따로 수행했다. (참 지저분하다)

 

 

public class Main {

    static int n;
    static int a[][];
    static int temp[][];
    static boolean visited[][];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        a = new int[n][n];
        visited = new boolean[n][n];
        
        int top = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
                if(top < a[i][j])
                    top = a[i][j];
            }
        }
        temp = a;
        
        int max = 0;
        for(int i=0; i<top; i++) {
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    visited[j][k] = false;
                }
            }
            dfs(0, 0, i);
            
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    visited[j][k] = false;
                }
            }
            
            int cnt = 0;
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    if(!visited[j][k] && temp[j][k] != 0) {
                        dfs(j, k);
                        cnt++;
                    }
                }
            }
            if(max < cnt)
                max = cnt;
        }
        System.out.println(max);
        sc.close();
    }
    
    public static void dfs(int x, int y) {
        if(temp[x][y] == 0)
            return;
        
        visited[x][y] = true;
        
        int mx[] = {1, 0, -1, 0};
        int my[] = {0, 1, 0, -1};
        
        for(int i=0; i<4; i++) {
            int nx = x + mx[i];
            int ny = y + my[i];
            
            if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                if(!visited[nx][ny])
                    dfs(nx, ny);
            }
        }
    }
    
    public static void dfs(int x, int y, int height) {
        visited[x][y] = true;
        
        if(a[x][y] <= height)
            temp[x][y] = 0;
        
        int mx[] = {1, 0, -1, 0};
        int my[] = {0, 1, 0, -1};
        
        for(int i=0; i<4; i++) {
            int nx = x + mx[i];
            int ny = y + my[i];
            
            if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                if(!visited[nx][ny])
                    dfs(nx, ny, height);
            }
        }
    }
}