[BOJ] 백준 2468 안전 영역

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

2468번: 안전 영역

 

 

---

 

풀이 방법

1. 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다. 비의 양보다 지점이 더 높을 경우, 안전한 영역이므로 그 영역의 개수를 구한다.
2. 비의 양에 따른 모든 경우를 다 조사해서 안전한 영역의 최대 갯수를 찾아야 하므로, 주어진 영역 높이의 최솟값부터 최댓값까지 모든 경우의 수를 탐색한다.
3. dfs를 사용해서 안전 영역의 갯수를 세고 모든 경우의 수를 비교해서 최댓값을 도출한다.

 

다음은 Java로 작성한 코드이다.

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

public class B2468 {
    private static final int [] dx = { -1, 1, 0, 0 }; // 상하좌우
    private static final int [] dy = { 0, 0, -1, 1 };
    private static int n;
    private static int [][] map;
    private static boolean [][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        visited = new boolean[n][n];

        int max = 0;
        int min = 100;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                max = Math.max(max, map[i][j]);
                min = Math.min(min, map[i][j]);
            }
        }

        int answer = 1;

        for (int height = max; height >= min; height--) {
            int count = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] > height && !visited[i][j]) {
                        dfs(i, j, height);
                        count++;
                    }
                }
            }

            visited = new boolean[n][n];
            answer = Math.max(answer, count);
        }

        System.out.println(answer);
    }

    private static void dfs(int x, int y, int height) {
        visited[x][y] = true;

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

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

}