[BOJ] 2468번 : 안전 영역

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
int n; 
int board[105][105]; 
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
queue<pair<int, int>> Q;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	int mx_ht = 0, mn_ht = INT_MAX;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			mx_ht = max(mx_ht, board[i][j]);
			mn_ht = min(mn_ht, board[i][j]);
		}
	}
	int mx_cnt = 1;
	for (int ht = mx_ht; ht >= mn_ht; ht--) {
		int isvis[105][105]; 
		int cnt = 0; 
		for (int j = 0; j < n; j++) fill(isvis[j], isvis[j] + n, 0);
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (isvis[j][k] || board[j][k] <= ht) continue;
				cnt++; 
				isvis[j][k] = 1; 
				Q.push({ j,k }); 
				while (!Q.empty()) {
					auto cur = Q.front(); Q.pop(); 
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir]; 
						int ny = cur.Y + dy[dir]; 
						if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
						if (isvis[nx][ny] || board[nx][ny] <= ht) continue;
						Q.push({ nx,ny });
						isvis[nx][ny] = 1;
					}
				}
			}
		}
		mx_cnt = max(mx_cnt, cnt);
	}
	cout << mx_cnt << '\n';
}

bfs를 이용해 풀었다. 이때, 모든 구역이 물에 잠기지 않을 수도 있다는 조건을 빼먹어서, 틀렸다. 따라서, mx_cnt = 1로 초기화해주어야 한다. 또한, isvis 배열을 초기화할 때, fill 함수를 사용했는데, fill(isvis [j], isvis [j] + n,0)이라는 것도 조심하자.