백준 2468 안전영역

접근 방법

public static boolean dfs(int[][] map, int x, int y, int depth){

- DFS 진행 

 

public static int simulation(int[][] map, int depth, int max)

- depth 이하의 숫자들 침수 시키기

- depth max값까지 침수 되지 않은 영역들 모두 탐색

 

헷갈렸던 케이스

- if(!visited[j][k] && map[j][k] > i){ ... } 부분이 헷갈렸었다. 즉, 숫자 1개만 독립적으로 있는 경우를 잘못 count 해주고 있었다.

3
9 1 1
1 1 9
9 9 9

소스

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

public class BOK_2468 {
    public static void main(String[] args) throws IOException {
        solution();
    }
    static boolean[][] visited;
    static int N;
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];

        int max = -1;
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] > max) max = map[i][j];
            }
        }

        int result = -1;
        for (int i = 0; i <= max; i++) {
            int cnt = 0;
            visited = new boolean[N][N];
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if(!visited[j][k] && map[j][k] > i){
//                        System.out.println(j+" "+k +" "+i);
                        cnt += dfs(map, j, k, i);
                    }
                }
            }
//            System.out.println(i+" "+cnt);
            result = Math.max(result, cnt);
        }
        System.out.println(result);
    }

    public static int dfs(int[][] map, int x, int y, int depth){
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        visited[x][y] = true;

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

            // 범위 내인지 확인
            if(nowX < N && nowY < N && nowX >= 0 && nowY >=0){
                // 방문하지 않았고, 물의 깊이가 depth 초과이면 안전구간 세기
                if(!visited[nowX][nowY] && map[nowX][nowY] > depth){
//                    check = true;
                    visited[nowX][nowY] = true;
                    dfs(map, nowX, nowY, depth);
                }
            }
        }
//        return check;
        return 1;
    }


}