백준 2468번 안전 영역 C++

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

bfs로 해결할 수 있는 문제이다. 입력을 받은 영역 중에 가장 높은 영역을 max_height 이라고 저장한 뒤, 

비가 안오는 경우부터 비가 max_height까지 오는 경우를 모두 검사해서 안전 영역이 제일 많은 경우를 찾았다.

각 지역에 홍수가 났는지를 알려주는 isFlood 2차원 벡터를 만들고 비의 높이에 따라 Init 함수를 통해 isFlood를 초기화 해주었다. 그리고 탐색할 때 visited 배열을 따로 만들기 번거로워서 방문한 안전 영역을 홍수가 난 곳으로 바꿔주면서 탐색을 하였다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

void Init(const vector<vector<int>> &v, vector<vector<bool>> &isFlood, int height, int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] <= height) {
				isFlood[i][j] = true;
			}
			else {
				isFlood[i][j] = false;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	int max_height = -1;
	vector<vector<int>> v(n, vector<int>(n));
	vector<vector<bool>> isFlood(n, vector<bool>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
			if (v[i][j] > max_height) {
				max_height = v[i][j];
			}
		}
	}
	queue<pair<int, int>> q;
	int ans = -1;
	for (int i = 0; i <= max_height; i++) {//비의 높이	
		int cnt = 0;
		Init(v, isFlood, i, n); //비의 높이에 따른 홍수여부 초기화
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				//bfs로 탐색
				if (!isFlood[j][k]) {
					q.push({ j,k });
					cnt++;
					while (!q.empty()) {
						auto a = q.front();
						q.pop();
						if (a.first - 1 >= 0 && !isFlood[a.first - 1][a.second]) {
							isFlood[a.first - 1][a.second] = true;
							q.push({ a.first - 1,a.second });
						}
						if (a.second + 1 < n && !isFlood[a.first][a.second + 1]) {
							isFlood[a.first][a.second + 1] = true;
							q.push({ a.first,a.second + 1 });
						}
						if (a.first + 1 < n && !isFlood[a.first + 1][a.second]) {
							isFlood[a.first + 1][a.second] = true;
							q.push({ a.first + 1,a.second });
						}
						if (a.second - 1 >= 0 && !isFlood[a.first][a.second - 1]) {
							isFlood[a.first][a.second - 1] = true;
							q.push({ a.first,a.second - 1 });
						}
					}
				}
			}
		}
		if (cnt > ans) {
			ans = cnt;
		}
	}
	cout << ans;
};