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

DFS, BFS 문제입니다.

각 지역의 높이가 주어졌을 때 물의 높이가 몇일 때
가장 많은 영역이 생성 되는지 구하는 문제입니다.

1~100까지 모든 경우를 구해봅니다.
x일때 x이하의 값들을 전부 0으로 한 후에
0이 아닌 값들을 DFS해서 방문처리 해주었습니다.
DFS가 종료되었을 때 count를 증가해주었고
이를 통해 높이가 x일때 count를 구할 수 있었습니다.
높이가 x일때 count중 가장 큰 값을 출력하여 문제를 해결하였습니다.

 

	#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int n;
int maxHeight = 0;
int maxCount = 1;
int map[110][110];
int visit[110][110];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };

void DFS(int a, int b)
{
	int y, x;
	visit[a][b] = 1;

	for (int i = 0; i < 4; ++i) {
		y = moveY[i] + a;
		x = moveX[i] + b;
		if (!visit[y][x] && map[y][x]) {
			DFS(y, x);
		}
	}
}

int main(int argc, char* argv[])
{
	int count = 0;

	cin >> n;

	memset(map, 0, sizeof(map));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> map[i][j];
			maxHeight = max(maxHeight, map[i][j]);
		}
	}

	for (int k = 1; k < maxHeight; ++k) {
		count = 0;
		memset(visit, 0, sizeof(visit));

		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (map[i][j] <= k) {
					map[i][j] = 0;
				}
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (map[i][j] && !visit[i][j]) {
					DFS(i, j);
					++count;
				}
			}
		}
		maxCount = max(maxCount, count);
	}

	cout << maxCount << endl;

	return 0;
}