안전 영역

문제: 안전 영역 (백준 2468번)

구조 분석

해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다.

1. 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽, 외쪽으로 인점해 있으며 그 크기가 최대인 영역을 만한다.
   • 이는 BFS나 DFS를 사용하여 해결할 수 있다.
   • DFS를 이용하여 안전 영역 덩어리를 세는 경우 stack을 이용하면 된다.
2. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 여역의 최대 개수를 구하여라
   • 이는 Brute force로 해결할 수 있다.
   • 비가 와서 잠길 수 있는 모든 높이에 대해 탐색을 시행하면 된다.
     정리해보면 다음과 같다. 우선 Brute force를 이용해 비가 와서 잠기는 모든 높이에 대해 반복문을 돌린다. 그리고 해당 반복문 안에서 BFS나 DFS를 통해 안전 영역 덩어리를 세어 최대값을 반환하면 된다.

풀이 방법

이는 최근에 한 번 접해본 유형이어서 크게 당황하지 않고 풀 수 있었다. 구조 분석에서 기술한 바와 같이 풀이를 실시했으며 이번에는 DFS를 이용해 탐색을 수행했다.

해당 풀이에서 안전 영역 덩어리를 세는 과정에서 큰 어려움이 있었다. 처음에는 잠긴 영역: 0, 안전 영역: 1로 설정한 뒤 방문한 영역에 대해서 고려하지 않아 계속해서 틀렸다. 또한 잠기는 영역이 없는 코너 케이스를 고려하지 않아서 애먹었다. 이를 해결하기 위해서 잠긴 영역: 0, 안전 영역: 1, 방문 영역: -1로 표기했고, 코너 케이스 고려하여 stack에서 pop할 때 count를 증가시키고, expand를 실시할 때 인접한 영역을 방문했다면 count를 뺴는 방식으로 수정했다. 또한 시작 카운터를 1로 설정해 아무 지역도 잠기지 않는 경우에 대해 코너 케이스 처리를 했다.

코드

#include <stdio.h>
#include <iostream>
#include <stack>
#define MAX(a,b) (a>b?a:b)
using namespace std;

int n;
int ans = 1;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int map[100][100];
int tmp[100][100];

void copy(int map[100][100], int tmp[100][100]) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            tmp[i][j] = map[i][j];
        }
    }
}

void rainDFS(int h) {
    stack<pair<int,int>> S;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (tmp[i][j] <= h) {
                // Check Unsafe
                tmp[i][j] = 0;
            }
            else {
                // Check Safe
                tmp[i][j] = 1;
                S.push(make_pair(i,j));
            }
        }
    }
    int cnt = 0;
    while (!S.empty()) {
        int x = S.top().first;
        int y = S.top().second;
        S.pop();
        if (tmp[x][y] == -1) continue;
        // Check visited
        tmp[x][y] = -1;
        cnt++;
        int flag = 0;
        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 (tmp[nx][ny] == 1) {
                    S.push(make_pair(nx,ny));
                }
                else if (tmp[nx][ny] == -1) {
                    flag = 1;
                }
            }
        }
        if (flag == 1) cnt--;
    }
    ans = MAX(ans, cnt);
}

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> map[i][j];
        }
    }

    for (int i=1; i<=100; i++) {
        copy(map, tmp);
        rainDFS(i);
    }
    cout << ans << "\n";
    return 0;
}  

정리

문제 구조 분석보다 코너 케이스 때문에 더 애먹었던 문제이다. 일반적으로 BFS나 DFS 문제는 방문 여부를 저장하기 위한 matrix를 추가로 만들어주지만, 한번에 처리하려고 시도했더니 조건문과 코너 케이스에 부딪쳐 고생했다.