[백준/C++] 2468 안전 영역

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

 

코드

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

#define MAX 101
int arr[MAX][MAX], ans = 0, dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 }, n;
bool visit[MAX][MAX];

void bfs(int x, int y, int h) {
	visit[x][y] = true;

	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < n && gy >= 0 && gy < n && !visit[gx][gy] && arr[gx][gy] > h) {
				visit[gx][gy] = true;
				q.push({ gx, gy });
			}
		}
	}
}

void init() {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			visit[i][j] = false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int h=0;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			h = max(h, arr[i][j]);
		}
	}

	for (int i = 0; i <= h; i++) {
		init();
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (arr[j][k] > i && !visit[j][k]) {
					bfs(j, k, i);
					cnt++;
				}
			}
			ans = max(cnt, ans);
		}
	}
	cout << ans;
	return 0;
}

 

설명

입력받을 정보들을 입력받으면서 최대 높이를 구한다. 이후 높이가 0일 때부터 최대 높이일 때까지 계속 bfs를 돌리면서 구역의 개수를 구한 뒤에 갱신해준다.

 

느낀 점

처음에는 문제를 보고 브루트포스로 bfs를 돌려도 될 지 순간 고민했는데 수의 범위가 적어서 바로 코드를 짰다.  비가 오지 않는 경우를 고려하지 않아서 한 번 틀렸다. 

 

그래서 바로 bfs를 돌릴 때 for문에서 시작을 i가 0일 때부터 하도록 설정하니  맞았다.