[Java] 백준 2468 : 안전 영역

문제 링크

1.

이전에 풀었던 기본적인 그래프 문제.

항상 BFS로만 풀어와서 이번에는 DFS로 풀어보았다. DFS가 좀 더 직관적인 것 같다.

 

 

2.

1. 가장 큰 높이 $h$ 부터 가장 낮은 $1$ 까지 높이를 하나씩 낮춰주며 기준을 잡는다.

2. 기준 높이 $h$ 보다 큰 영역은 물에 잠기지 않으므로 그러한 영역의 개수를 구한다.

3. 영역의 개수의 최대값을 출력한다.

 

이하 코드 참고

 

 

3.

import java.util.Scanner;

public class Main {
    static int[][] area;
    static int n;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        area = new int[n][n];
        int maxH = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                area[i][j] = sc.nextInt();
                maxH = Math.max(maxH, area[i][j]);
            }
        }

        int cnt = 1;
        for (int h = maxH; h > 0; h--) {
            int tempCnt = 0;
            boolean[][] visited = new boolean[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (area[i][j] > h && !visited[i][j]) {
                        tempCnt += dfs(i, j, h, visited);
                    }
                }
            }
            cnt = Math.max(cnt, tempCnt);
        }

        System.out.println(cnt);
        sc.close();
    }

    static int dfs(int x, int y, int h, boolean[][] visited) {
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };

        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (area[nx][ny] > h && !visited[nx][ny]) {
                    dfs(nx, ny, h, visited);
                }
            }
        }

        return 1;
    }
}

 

 

4.

none