[BFS, 난이도 중하] 백준 2468번 안전 영역

Case(물에 잠기는 최대 높이)별로 안전 지역이 모두 다르기 때문에

casemap이라는 임시 배열을 두었다.

map배열의 각각 요소에 물에 잠기는 최대 높이를 빼준 배열이 casemap이 된다.

즉 casemap배열의 요소가 1이상이면 그 좌표는 안전 영역이 되는 것이다.

이 casemap 배열로 BFS를 수행하여 while문을 탈출할 때마다 group변수에 1을 추가하여 몇 개의 안전 영역 그룹이 생기는지 계산한다.

물에 잠기는 최대 높이를 1부터 99까지 99가지 경우에 대해 탐색하여 케이스별 group을 구해내면 된다.

케이스가 종료 될 때마다 ans의 최댓값을 업데이트 해나가며, 모든 케이스를 다 탐색 했을 때 최종 ans 값이 이 문제의 해답이 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
int map[101][101];
int casemap[101][101];
bool visited[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int maxi(int a, int b) {
	if (a > b) return a;
	else return b;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	int ans = 1;
	queue<pair<int, int> > q;
	int year = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int t = 1; t < 100; t++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				casemap[i][j] = map[i][j] - t;
				if (casemap[i][j] < 0) casemap[i][j] = 0;
			}
		}
		int group = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (casemap[i][j] >= 1 && !visited[i][j]) {
					visited[i][j] = true;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						int x = q.front().first;
						int y = q.front().second;
						q.pop();
						for (int k = 0; k < 4; k++) {
							if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
							if (casemap[x + dx[k]][y + dy[k]] >= 1 && !visited[x + dx[k]][y + dy[k]]) {
								q.push(make_pair(x + dx[k], y + dy[k]));
								visited[x + dx[k]][y + dy[k]] = true;
							}
						}
					}
					group++;
				}
			}
		}
		memset(visited, false, sizeof(visited));
		memset(casemap, 0, sizeof(casemap));
		ans = maxi(ans, group);
	}
	cout << ans;
}