백준 2468 안전 영역(c++)

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

2468번: 안전 영역

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int h;
int board[101][101];
bool visited[101][101];
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int maxh = 0;
void dfs(int x,int y,int num)
{
	visited[x][y] = true;
	for(int i=0;i<4;i++)
	{
		int r = x + mov[i][0];
		int c = y + mov[i][1];
		if(r<h && c<h && r>=0 && c>=0 && board[r][c]>num && !visited[r][c]){
			dfs(r,c,num);
		}
	}
	
}
int main()
{
	cin>>h;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<h;j++)
		{
			cin>>board[i][j];
			if(board[i][j]>maxh){
				maxh = board[i][j];
			}
		}
	}
	
		int result = 0;	
		for(int number = maxh;number>=0;number--)
		{
			memset(visited,0,sizeof(visited));
			int cnt=0;
				for(int i=0;i<h;i++)
					{
				for(int j=0;j<h;j++)
					{
					if(board[i][j]>number && !visited[i][j]){
					cnt++;
					dfs(i,j,number);	
					}
					if(cnt>result) result =cnt;
				}
			}	
		}
	
		cout<<result;

	
	
	
}

<풀이 과정>

dfs를 이용한 풀이이다.

우선적으로 N*N 영역에서 영역의 최대 높이를 구하기 위해서 maxh라는 최대높이변수를 만들어줬다.

변수를 입력받을 때 마다 변수가 maxh보다 크다면, 최대높이변수를 갱신시켜주면 된다.

최대 높이 변수 최대치에서 높이가 0이 될 때까지의 각각 안전영역의 개수를 구해준 다음,

안전영역의 개수가 이전 안전영역의 개수보다 크다면 갱신해주면 된다.

높이가 0인 부분은 장마가 오지 않았다고 생각하면 이해하기 쉬울 것이다.