백준 2468번 안전 영역 [DFS] :: 마이구미

이번 글은 백준 알고리즘 문제 2468번 "안전 영역" 을 다뤄본다.

정올 초등부에서 출제된 문제이다.

초등부이지만, 정답률은 30%인 것을 볼 수 있다.

DFS, BFS - http://mygumi.tistory.com/102

문제 접근은 DFS 또는 BFS를 활용할 수 있다.

기본적인으로 DFS 및 BFS 기본 지식을 가지고 있다면 충분히 풀 수 있다.

여기서는 DFS를 통해 문제를 풀어보겠다.

위 그림은 높이가 4와 6의 경우를 나타내고 있다.

흰색 영역의 수를 찾는 문제가 된다.

그래프에서는 이 영역을, 연결 요소의 개수라고 볼 수 있다.

즉, DFS 탐색이 이루어지는 횟수 중 가장 큰 수가 정답이 된다.

높이를 1부터 100까지 경우 각각 DFS 탐색을 하면 된다.

public static void dfs(int[][] array, boolean[][] visited, int y, int x, int h) {
    if (visited[y][x]) {
        return;
    }

    visited[y][x] = 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 (array[ny][nx] > h && !visited[ny][nx]) {
                dfs(array, visited, ny, nx, h);
            }
        }
    }
}

주의할 점은 본인의 경우에는 초기 값을 0으로 할당했다.

하지만 문제의 최소 답은 어느 것도 잠기지 않는다면 하나의 영역임으로써, 1이 된다.

위 소스에서는 x,y 좌표의 개념을 활용한 변수 이름을 지정하였다.

백준 알고리즘 2468번 안전 영역 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/2468.java