[C++] 백준 2468번 - 안전영역

문제 조건에 

아무 지역도 물에 잠기지 않을 수도 있다.

이 말을 듣고 음 그런군..... 이라고 생각을 했었는데

이것때문에 계속 틀렸다;;;

이 말은 즉슨 level이 0부터 시작될 수도 있다는거다

 

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

int n, safe, level;
int map[101][101];
bool visited[101][101];
int map_copy[101][101];
vector<int> v;

const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

void copy(int flood_level) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] > flood_level)
				map_copy[i][j] = 1;
		}
	}
}

void bfs(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = true;
	q.push({ y, x });

	while (!q.empty()) {
		auto current = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = current.second + dx[dir];
			int ny = current.first + dy[dir];

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[ny][nx] || map_copy[ny][nx] == 0) continue;
			q.push({ ny, nx });
			visited[ny][nx] = true;
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	int max_level = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (max_level < map[i][j])
				max_level = map[i][j];
		}
	}

	for (int k = 0; k <= max_level; k++) {
		copy(k);
		int count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map_copy[i][j] && !visited[i][j]) {
					bfs(i, j);
					count++;
				}
			}
		}
		v.emplace_back(count);

		memset(map_copy, 0, sizeof(map_copy));
		memset(visited, false, sizeof(visited));
	}

	sort(v.begin(), v.end());

	cout << v[v.size() - 1] << '\n';

	return 0;

}