안전 영역 C++ - 백준 2468

https://acmicpc.net/problem/2468

이 문제는 백준 1012와 유사한 문제이다.

수위를 0부터 지대의 최대 높이 전까지의 경우를 dfs를 사용하여

모두 확인하고 최대 안전 영역을 그때 마다 갱신하면 되는 문제이다.

#include <bits/stdc++.h>
#define MAX 100
using namespace std;

int imap[MAX][MAX];
int vis[MAX][MAX];
int n;
int maxi=0;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int ans=0;
int tans;
int lv;

void dfs(int x, int y){
	vis[x][y]=true;
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		
		if(0<=nx && nx<n && 0<=ny && ny<n && imap[nx][ny]>lv && !vis[nx][ny]){
			dfs(nx,ny);
		}
	}
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin >> imap[i][j];
			maxi=max(maxi,imap[i][j]);
		}
	}
	for(lv=0;lv<maxi;lv++){
		int tans=0;
		memset(vis,false,sizeof(vis));
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(imap[j][k]>lv && !vis[j][k]){
					dfs(j,k);
					tans++;
				}
			}
		}
		ans=max(tans,ans);
	}
	cout << ans;
}