[알고리즘][DFS][2468] 안전영역 (JAVA)

[알고리즘][DFS][2468] 안전영역 (JAVA)

문제

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

풀이

문제를 처음에 이해하지 못해서 다시 풀었습니다ㅠㅠ 가장 높은 층이 5층이라면 1층부터 5층까지 비에 잠길 때 경우를 모두 카운팅해줘야 합니다. 저는 n층 이상인줄 알고 삽질을 하고 방황하다 다시 풀게 되었습니다. 독해력을 더 키워야겠어요.....

가장 높은 층의 값을 구한 뒤, 층 수(k)를 고정시키고 k값 이상인 층들을 모두 방문하며 영역을 카운팅하면 됩니다. DFS를 몇 문제 풀어보니 유사한 패턴의 문제가 있는 것 같아 전보다는 푸는 시간이 덜 걸렸네요.

그리고 check배열을 초기화 시켜주지 않아서 한참 들여다 보고 있었습니다.ㅠㅠ 다음에는 이런 실수 하지 말아야지...! 

코드

package algorithm_DFS;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class q_2468_2 {
    static int n = 0;
    static int[][] data;
    static int[][] check;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    public static void dfs(int x,int y,int aux) {
        check[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(check[nx][ny] == 0 && data[nx][ny]>=aux) {
                    dfs(nx, ny, aux);
                }                
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Scanner scan = new Scanner(System.in);
        int cnt = 0; 
        int max_val = 0;                                     
        n = Integer.parseInt(st.nextToken());                                
        data = new int[n][n];
        
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++) {
                data[i][j]= Integer.parseInt(st.nextToken());
                if(max_val<data[i][j]) max_val=data[i][j]; 
            }
        }
        int max_cnt = 1;
        
        for(int k=1;k<=max_val;k++) {
            cnt=0;
            check = new int[n][n];    
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    if(data[i][j]>=k && check[i][j]==0) {
                        cnt++;
                        dfs(i,j,k);
                    }
                }
            }
            if(max_cnt < cnt) max_cnt=cnt;
        }
        System.out.println(max_cnt);
    }
 
}