[백준/Java] 2468번 안전영역

어떻게 풀어야 할까

항상 문제는 Brute Force를 먼저 생각한다. 문제를 보자마자 어떤 알고리즘을 사용해서 어떻게 풀어야 할지 아는 것이 가능할까. 적어도 나는 안된다... 그렇기 때문에 일단 문제의 정답을 구할 수 있는 알고리즘을 구하고, 문제에서 요구하는 시간 복잡도 안에 해결하기 위해 최적화를 진행한다.

해당 문제는 물에 잠기지 않은 영역의 갯수 중 최대값을 구하는 문제이다. 물의 높이는 선형적으로 점차 증가하고, 각각의 경우의 수를 기록하여 그 중 최대값을 출력하면 된다. 물에 잠기지 않는 안전 영역은 DFS를 통해서 구할 수 있다. DFS를 통해 연결 요소를 각각의 영역에서 반복한다, 즉 안전 영역의 갯수를 물에 아직 잠기지 않고, 방문한적 없는 모든 영역에서 DFS를 통해 DFS가 실행되는 횟수가 곧 안전 영역의 수이다.

결국 DFS + Brute Force 로 해당 문제를 풀 수 있다.

 

시간 복잡도

해당 문제를 어떻게 풀어야 할지 알았으면 해당 알고리즘이 시간 내에 가능한지 생각해봐야 한다. 최악의 경우를 생각해보자. 최악의 경우는 가로 세로가 100 이고, 물의 높이가 1~100까지 모두 존재하는 경우일 것이다. 해당 경우의 시간 복잡도는 모든 물의 높이를 계산해야 하므로 N, 각 영역에 대해 DFS를 돌리는 횟수 (N + 1) * N / 2, DFS의 시간복잡도 O(n+e), 결국 O(N^3(n+e)) -> O(N^4) 이고 N <= 100 이므로 해당 문제는 1초안에 풀 수 있다.

 

문제 풀이 알고리즘

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

public class Main {

    static int N, maxWaterDepth, maxSafeZoneCnt;
    static int[][] sunkPos;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        input();
        findMaxSafeZone();
        output();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        sunkPos = new int[N][N];
        visited = new boolean[N][N];
        maxWaterDepth = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                sunkPos[i][j] = Integer.parseInt(st.nextToken());

                if (maxWaterDepth < sunkPos[i][j]) {
                    maxWaterDepth = sunkPos[i][j];
                }
            }
        }
    }

    public static void findMaxSafeZone() {
        maxSafeZoneCnt = 0;
        for (int waterDepth = 0; waterDepth < maxWaterDepth + 1; waterDepth++) {
            visited = new boolean[N][N];
            int safeZoneCnt = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && sunkPos[i][j] > waterDepth) {
                        safeZoneCnt += DFS(i, j, waterDepth);
                    }

                }
            }
            maxSafeZoneCnt = Math.max(maxSafeZoneCnt, safeZoneCnt);
        }
    }

    public static int DFS(int x, int y, int waterDepth) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newY >= 0 && newX < N && newY < N) {
                if (!visited[newX][newY] && sunkPos[newX][newY] > waterDepth) {
                    DFS(newX, newY, waterDepth);
                }
            }
        }
        return 1;
    }

    public static void output() {
        System.out.println(maxSafeZoneCnt);
    }
}

 

문제 풀이는 위에서 설명한 DFS + Brute Force 를 그대로 구현해주면 된다. maxWaterDepth를 따로 구해준 이유는 어차피 최대 값을 넘어서는 비가 오면, 모든 영역이 잠기기 때문에 구할 필요가 없기 때문이다.

 

참고: 물의 높이가 최대 N인지 모르고, 테스트 케이스만 보고 1자리 수만 된다고 생각했다. 그리고 틀렸다... 항상 문제를 잘 읽어서 조건을 잘 체크하자.