[백준 2468] 안전 영역, C++

 본 문제는 '2010 한국정보올림피아드 초등부 2번' 문제다. 장마철에 물에 잠지기 않는 안전 구역의 최대 개수를 구하는 문제다.

1. 기준값 0 ~ 배열의 최댓값까지 반복
   1. 기준값보다 높은 지역 개수 구하기
   2. 제일 큰 안전 구역의 개수 구하기

#include <cstdio>
#include <queue>
#include <cstring>
 
using namespace std;
 
int d[101][101];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool chk[101][101];
 
int main() {
    int n, max = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &d[i][j]);
            if (max < d[i][j]) max = d[i][j];
        }
    }
    queue<pair<int, int>> q;
    int index = 0;
    int ans = 0;
    // 기준 이용하여 범람지역 확인
    while (index != max) {
        int cnt = 0;
        memset(chk, false, sizeof(chk));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 기준값 보다 높을 때
                if (d[i][j] > index && !chk[i][j]) {
                    q.push(make_pair(i, j));
                    chk[i][j] = true;
                    cnt += 1;
                    while (!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        for (int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                                if (d[nx][ny] > index && !chk[nx][ny]) {
                                    q.push(make_pair(nx, ny));
                                    chk[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
        index += 1;
        // 범람 구역의 최대값 찾기
        if (ans < cnt) ans = cnt;
    }
    printf("%d", ans);
    return 0;
}