[백준/BOJ] 2468번 안전 영역 (C++)

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

2468번: 안전 영역

BFS 문제, map의 값이 전부 1일 때 답이 1이 나와야 하는데, 이를 주의해야 한다. (비가 안오는 경우도 있으므로)

 

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

int n, answer;
int map[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool visit[101][101];

void BFS(int sx, int sy, int h) {
	queue<pair<int, int> > q;
	q.push({ sx, sy });
	visit[sx][sy] = true;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if(map[nx][ny] >= h && !visit[nx][ny]) {
				q.push({ nx, ny });
				visit[nx][ny] = true;
			}
		}
	}
}

int main(void) {
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);

	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	
	// 비가 안오고(h = 0), map이 전부 1일 때 답이 1이 나와야 한다.
	for(int h = 0; h <= 100; h++) {
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(map[i][j] >= h && !visit[i][j]) {
					BFS(i, j, h);
					cnt++;
				}
			}
		}
		memset(visit, false, sizeof(visit));
		answer = max(answer, cnt);
	}
	
	cout << answer;
}