문제 링크

코드 설명

DFS를 이용하여, 각각의 비가오는 높이를 하나씩 늘려가며 전체 map을 탐색하였다. 그중 비의 높이에따른 안전영역이 가장 넓은(cnt) 를 계속해서 갱신하였다.
DFS를 연습하기 좋은 문제였다.

소스 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
	int n;
	int map[101][101];
	int hei;
	int low;
	int visit[101][101];
	int dy[] = { -1,1,0,0 };
	int dx[] = { 0,0,1,-1 };
	int result;
	void dfs(int y, int x,int rain) {

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
		
			if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
			if (map[ny][nx]<=rain || visit[ny][nx]) continue;

			visit[ny][nx] = true;
			dfs(ny, nx, rain);

		}
		

	



}
int main() {
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
			 hei = max(hei, map[y][x]);
			 low = min(low, map[y][x]);
		}
	}
	
	for (int i = low; i < hei; i++) {

		int cnt = 0;
		memset(visit,false, sizeof(visit)); //높이 바뀌기전 (dfs 돌기전) visit배열 초기화 매번 해주기 
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {

				if (map[y][x] > i && !visit[y][x]) {
					visit[y][x] = true;
					cnt++;
					dfs(y, x,i);

				}

			}
		}
		result = max(result, cnt);

	}
	cout << result;
	




	return 0;
}