[BOJ] #2468 안전 영역

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

2468번: 안전 영역

---

요 근래에 BFS를 활용한 문제들을 계속 풀어보고 있는데, 이제 좀 감이 생긴 듯 하다. 문제 접근방식도 그렇고 풀이 과정에 있어서도 나름 매끄럽게 풀었던 문제라 생각한다.

이 문제의 요점은 다음과 같다. 나타날 수 있는 테스트 케이스에 대해 특정한 조건마다 브루트포스 방식으로 순회하며 BFS로 같은 영역을 구하는 것이다. 어차피 맥시멈이 100인 케이스밖에 다루지 않기 때문에 조건문이 3-4개가 중첩된다 하더라도 1초의 시간제한에 걸릴수 없다. 

풀이 과정에서 크게 간과했던 부분이 2가지 있었는데 첫번째는, 각각의 테스트 케이스마다 visited 배열을 다시 false로 초기화 해주어야 한다는 것이고 두번째는, 아예 비가 오지않는 경우도 있기에 1~100까지 브루트포스를 돌리는것이 아닌 0~100까지 돌리는 것이다. 질문 게시판에 올라온 질문들 대다수가 1~100으로 범위를 잘못 잡은 것들이던데, 많이들 이 부분에서 실수하는것 같다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 101

using namespace std;

int N;
int arr[MAX][MAX];
bool visited[MAX][MAX] = { false };

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

void BFS(int x, int y, int idx) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX >= 0 && newX < N) && (newY >= 0 && newY < N)
                && visited[newX][newY] == false) {
                if (arr[newX][newY] > idx) {
                    Q.push(make_pair(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
    }
}
void F(int n) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            visited[i][j] = false;
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int a;
            cin >> a;

            arr[i][j] = a;
        }
    }   //배열 입력

    vector<int> total;
    for (int idx=0; idx<101; idx++) {
        F(N);
        int cnt = 0;

        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j] == false && arr[i][j] > idx) {
                    BFS(i,j,idx);
                    cnt++;
                }
            }
        }

        total.push_back(cnt);
    }
    sort(total.begin(), total.end());

    cout << total.back() << '\n';

    return 0;
}