안전 영역

문제 정보

• 사이트 : 백준 알고리즘 사이트
• 문제 번호 : 2468
• 문제 분류 : dfs
• 난이도 : silver 1

문제 풀이

내가 짠 코드

생각한 문제 조건
1. 높이 제한 = depth
2. depth 이하의 지역은 물에 잠긴다.
3. 물에 안잠긴 상하좌우로 이어진 곳을 안전한 영역이라 한다.
4. 각 지역은 1이상 100 이하의 정수이다.
5. 맵의 크기인 n은 2이상 100이하의 정수이다.
6. 안전한 영역의 최대 개수를 구한다.

💭 생각 노트

• n이 2이상 100이하이므로 연결행렬로 구현하여도 성능이 괜찮을 것 같다.
• while문으로 물의 높이를 1씩 증가시키며 그때의 안전한 영역의 개수를 현재 결과와 비교해 결과를 변경한다.
• 물의 높이에 대한 연산이 끝난 뒤엔 다음 높이에 대한 dfs 수행을 위해 visit를 리셋한다.
• 물의 높이가 가장 높은 지점의 높이와 같다면 안전 영역이 0이므로 depth는 1이상 maxHeight-1이하까지만 확인해주면 된다.
• result는 처음에 0으로 초기화 해주었지만 (전 지역의 높이가 1인경우 결과는 0) 문제를 내려보니 노트에 아래와 같이 아무 지역도 물에 잠기지 않을 수 있으므로 1로 초기화 해준다.
  

public class BJ_2468 {
    private static int n;
    private static int[][] map;
    private static boolean[][] visit;
    private static int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int result = 1;
    private static int maxHeight = Integer.MIN_VALUE;
    private static int depth = 1;

    public static void dfs(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int dx = x + check[i][0];
            int dy = y + check[i][1];
            if(0 <= dx && dx < n && 0 <= dy && dy < n){
                if(!visit[dx][dy] && map[dx][dy] > depth){
                    visit[dx][dy] = true;
                    dfs(dx,dy);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visit = new boolean[n][n];


        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }

        while(depth < maxHeight){
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(!visit[i][j] && map[i][j] > depth) {
                        count++;
                        visit[i][j] = true;
                        dfs(i, j);
                    }
                }
            }
            result = Math.max(result, count);
            for (int i = 0; i < n; i++) {
                Arrays.fill(visit[i],false);
            }
            depth ++;
        }

        System.out.println(result);
        br.close();
    }
}

문제 출처

• 안전 영역

썸네일 출처

Image by storyset on Freepik