[백준] 2468번 안전영역

2468번: 안전 영역

BFS로 풀었다.

#include <iostream> 
#include <vector> 
#include <queue> 
#include <algorithm>
using namespace std;

int n;
vector<int> countAll;

int main() {
	countAll.push_back(1);
	cin >> n;
	vector<vector<int>> height(n);
	vector<vector<int>> rain(n);
	for (int i = 0; i < n; i++) {
		height[i] = vector<int>(n);
		rain[i] = vector<int>(n);
	}
	int maxHeight = 0;
	int minHeight = 101;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> height[i][j];
			if (height[i][j] > maxHeight) maxHeight = height[i][j];
			if (height[i][j] < minHeight) minHeight = height[i][j];
		}
	}
	for (int rainAmount = minHeight; rainAmount <= maxHeight; rainAmount++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (height[i][j] <= rainAmount) {
					rain[i][j] = 1;
				}
			}
		}

		int count = 0;
		vector<vector<bool>> visited(n);
		for (int i = 0; i < n; i++) {
			visited[i] = vector<bool>(n);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j] && rain[i][j] == 0) {
					count++;
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && rain[cur.first + 1][cur.second] == 0) {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && rain[cur.first - 1][cur.second] == 0) {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && rain[cur.first][cur.second + 1] == 0) {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && rain[cur.first][cur.second - 1] == 0) {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
			}
		}
		countAll.push_back(count);
	}
	int maxCount = 0;
	for (int i : countAll)
		if (i > maxCount) maxCount = i;
	cout << maxCount;
	return 0;
}