백준 2468 - 안전 영역

문제

 

 

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

2468번: 안전 영역

 

 

 

코드

 

 

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.ArrayDeque;

public class Main {

    // 상, 하, 좌, 우
    private static int[] dy = {0, 0, -1, 1};
    private static int[] dx = {-1, 1, 0, 0};
    private static int N, highst = 0;
    private static int max, count = 0;
    private static int[][] input, visitB, visitD;

    public static void main(String[] args) throws Exception {
        
        // N 및 input 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        input = new int[N][N];
        //visit = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
                // 제일 높은 곳 구하기
                if(highst < input[i][j]) highst = input[i][j];
            }
        }

        // N번 반복하며 침수 -> 탐색 -> clear 반복
        // 비가 아예 안왔을 때도 세야함.
        for(int i = 0; i < highst+1; i++) {
            
            // 침수 -> dfs에서 하는게 시간 줄이기 될듯.
            //drop(i+1);
            
            // 탐색
            // bfs로 안전지대들 Que에 넣음 -> Que에서 빼면서 dfs 진행
            visitB = new int[N][N];
            visitD = new int[N][N];
            count = 0;
            bfs(i);

            //System.out.println("level " + (i+1) + "의 count 크기 : " + count);
            if(count > max)  max = count;
            //dfs(0, 0, 0, i+1);

            // 초기화 - visit 초기화 -> 새로 만드는걸로 초기화
            //clearMap();
        }

        // 결과 출력
        System.out.println(max);
    }

    // map 침수시키는 함수
    // k는 잠기는 높이
    // public static void drop(int k) {
    //     for(int i = 0; i < N; i++) {
    //         for(int j = 0; j < N; j++) {
    //             if(input[i][j] <= k) map[i][j] = 1;
    //             else map[i][j] = 0;
    //         }
    //     }
    // }


    // bfs 함수
    // level = 침수 높이
    public static void bfs(int level) {

        // queD 생성
        Queue<int[]> queB = new ArrayDeque<int[]>();
        Queue<int[]> queD = new ArrayDeque<int[]>();

        // queB에 0,0 제공
        visitB[0][0] = 1;
        queB.offer(new int[] {0, 0});

        // 안전지대인지 확인 후 안전지대이면 queD에 넣기
        if(input[0][0] > level)
            queD.offer(new int[] {0, 0});

        // bfs 시작
        while(!queB.isEmpty()) {

            // 단계 나누기 -> 여기서는 필요없음.
            //int size = queB.size();

            // 현재 위치 뽑기.
            int[] cur = queB.poll();
            int cx = cur[0];
            int cy = cur[1];

            // 4방 탐색 진행.
            for(int i = 0; i < 4; i++) {
                int tx = cx + dx[i];
                int ty = cy + dy[i];

                // 경계 여부, visitB 여부 확인
                if(tx >= 0 && tx < N && ty >= 0 && ty < N && visitB[tx][ty] == 0) {
                    // 탐색 표시
                    visitB[tx][ty] = 1;
                    queB.offer(new int[] {tx, ty});

                    // 안전지대인지 확인 후 안전지대이면 queD에 넣기
                    if(input[tx][ty] > level)
                    queD.offer(new int[] {tx, ty});
                }
            }

        } // 안전지대가 전부 queD안에 들어감.

        //System.out.println("level " + level + "의 queD 크기 : " + queD.size());

        // dfs 시작
        while(!queD.isEmpty()) {
            // queD에 저장했던 좌표들 dfs 시작
            // 현재 위치 뽑기.
            int[] cur = queD.poll();
            int cx = cur[0];
            int cy = cur[1];

            // 만약 해당 칸이 visitD된 적 없다면 count + 1
            // 이후 dfs로 채워주기 -> bfs로 해도 될듯.
            if(visitD[cx][cy] == 0) {
                count++;
                visitD[cx][cy] = 1;
                dfs(cx, cy, level);
            }
        }

    }

    // dfs 함수
    // x좌표, y좌표, 단계, 침수높이
    public static void dfs(int x, int y, int level) {

        // 4방 탐색 진행하며 visitD 채워주기
        for(int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];

            // 경계 여부, visitB 여부, 안전지대 여부 확인
            if(tx >= 0 && tx < N && ty >= 0 && ty < N && visitD[tx][ty] == 0 && input[tx][ty] > level) {
                visitD[tx][ty] = 1;
                dfs(tx, ty, level);
            }
        }
    }


    // map clear 함수
    // public static void clearMap() {
    //     for(int i = 0; i < N; i++) {
    //         for(int j = 0; j < N; j++) {
    //             map[i][j] = 0;
    //             visit[i][j] = 0;
    //         }
    //     }
    // }
}

 

 

 

해설

 

 

  백준의 2468번 문제 '안전 영역' 입니다.

 

굉장히 오랜만에 풀어본 알고리즘이어서 이게 과연 실버1에 맞는 난이도인지는 잘 모르겠습니다. 문제는 아래와 같습니다.

 

  굴곡이 있는 지형이 있다고 가정하면 비가 옴에 따라 점차 지대가 낮은 곳부터 잠기게 되겠지요. 1단계씩 점점 잠길 때마다 비로부터 안전한 영역이 달라질텐데 이를 안전 영역이라고 합니다. 해서 특정 단계 때 다른 단계에 비해 안전 영역의 갯수가 많아지는 때가 올텐데, 그 때의 안전 영역 갯수를 구하는 문제입니다.

 

  설명은 어려운데 단순히 이야기하자면 맵에 n보다 큰 숫자가 연속적으로 있는 타일이 몇 덩이 존재하는지 세고, 그 덩이의 갯수가 가장 많았을 때의 덩이의 갯수를 출력하는 문제입니다.

 

  우선 탐색문제이므로 bfs와 dfs 중에 골라야 할텐데요. 처음에는 dfs인줄 알았는데, 어떤 방법을 써도 1번의 탐색만으로 알 수가 없습니다. 제일 높은 지형의 높이만큼 반복을 해야되기 때문에 처음부터 어느 타일이 안전 영역인지 미리 큐에 넣어놓을 수 없기 때문입니다.

 

  따라서 저는 우선 제일 높은 지형의 높이에 1을 더한 만큼 bfs를 반복하였습니다. 이유는 비가 아예 내리지 않았을 경우도 탐색을 해야하기 때문입니다. 아니면 마지막에 답을 출력해줄 변수의 기본값을 1로 둔채 제일 높은 지형의 높이만큼만 반복해도 좋겠네요.

 

  그리고 각 bfs에서는 아래와 같은 단계를 거쳤습니다.

 

1. bfs를 통해 맵을 전부 탐색하면서 안전 영역인 좌표를 dfs에 쓸 큐에 넣어줍니다.
2. bfs를 마친 후, dfs용으로 만들어 놓은 큐에 있는 좌표들을 전부 dfs 해줍니다.
   1. 이 때, dfs용 visit 배열을 확인하면서 이미 dfs가 지나간 곳은 굳이 들어가지 않습니다.
   2. 이로 인해 만일 dfs용 큐에서 뽑은 좌표의 visit을 확인했을 때 막혀있지 않다면 그것이 한 덩이의 안전 영역을 처음으로 dfs로 탐색한다는 보장을 해줍니다.
   3. 따라서 dfs를 실행할 때마다 안전 영역이 몇개인지 카운트하는 변수를 +1 해줍니다.

 

  마지막으로 bfs를 마쳤을 때 해당 단계의 안전 영역이 다른 단계의 안전 영역보다 많은지 비교해주는 프로세스를 넣으면 마무리됩니다.

 

  해보지는 않았으나 아마 dfs부분을 다시 bfs로 변경해도 알고리즘은 잘 동작할 것 같습니다.

 

 

 

어려움 포인트

 

 

  이미 문제를 많이 푸셨던 분들이라면 금방 풀고 넘어가셨겠지만 저에게는 나름 어려웠던 문제였습니다. 그 이유는 크게 2가지였습니다.

 

1. 탐색을 2번 사용해야 한다.
2. 하나의 안전 영역이 끝나는 조건을 설정하는 것이 어려웠다.
   1. 안전 영역이 총 몇개인지 셀 수 있으려면 한개의 안전 영역을 셀 수 있어야 하는데, 그 조건을 생각해내기 힘들었습니다.

1. 이 때, dfs용 visit 배열을 확인하면서 이미 dfs가 지나간 곳은 굳이 들어가지 않습니다.
2. 이로 인해 만일 dfs용 큐에서 뽑은 좌표의 visit을 확인했을 때 막혀있지 않다면 그것이 한 덩이의 안전 영역을 처음으로 dfs로 탐색한다는 보장을 해줍니다.
3. 따라서 dfs를 실행할 때마다 안전 영역이 몇개인지 카운트하는 변수를 +1 해줍니다.

'한개의 안전 영역을 셀 수 있다'는 것은 이 부분을 의미합니다.