[BOJ] 백준 2468 - 안전 영역 풀이

1. 문제

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

2468번: 안전 영역

 

2. 풀이

생각보다 삽질을 많이 한 문제였다. 처음에는 '빗물의 높이를 모르는데 어떻게 구하지?'라고 생각했는데 문제를 다시 잘 읽어보니 '비의 양에 따른 모든 경우를 다 조사해보면'이라는 문구를 보고 브루트포스를 떠올렸고 탐색을 하며 최대 개수를 구하는 문제니 DFS나 BFS를 생각했다. 여기서는 DFS로 문제를 해결하였다.

브루트포스를 돌릴 때 주의해야할 점은 노트에 적혀있는대로 '아무 지역도 물에 잠기지 않을 수도 있다.'라는 것이다. 이 때문에 입력으로 주어지는 높이의 범위가 1 이상 100이하의 정수이므로 브루트 포스는 0부터 시작해야 한다.

영역의 높이를 저장할 map 배열과 잠기는 곳을 표시한 bin_map 배열, 방문처리에 필요한 visited 배열을 초기화해준다. 방문처리를 안했고 bin_map 배열의 값이 1이고 (이때 1이라는 건 잠기지 않은 곳을 의미한다) 방문하지 않았다면 개수를 카운트하여 dfs 함수를 실행한다. 그리고 브루트포스 알고리즘 마지막에 dfs 한바퀴를 돌린 값과 현재의 최대 개수를 비교하여 갱신하고 브루트 포스를 다 돌린 후에 최대 개수를 출력한다. (bin_map 배열은 다른 블로그 분의 풀이를 참고하였다.)

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {
    static int N;
    static int[][] map;
    static int[][] bin_map;
    static boolean[][] visited;

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int max = 0;
    static int tempResult = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        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());
            }
        }

        for (int k = 0; k <= 100; k++) {
            bin_map = new int[N][N];
            visited = new boolean[N][N];
            tempResult = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] <= k) {
                        bin_map[i][j] = 0;
                    }
                    else {
                        bin_map[i][j] = 1;
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (bin_map[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);
                        tempResult += 1;
                    }
                }
            }
            max = Math.max(max, tempResult);
        }
        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
        br.close();
    }

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

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

            if (xF >= 0 && yF >= 0 && xF < N && yF < N && !visited[xF][yF] && bin_map[xF][yF] == 1) {
                dfs(xF, yF);
            }
        }
    }
}