[백준/BOJ] 백준 2468번 : 안전 영역

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

2468번: 안전 영역

지역이 모두 물에 잠기지 않을 경우부터, 모두 물에 잠기기 직전까지 고려하여 안전영역의 개수가 가장 많은 경우의 안전영역의 개수를 구한다. 안전영역의 개수를 구하는 방법은 안전영역을 발견하면 그 안전영역에 해당하는 지역들을 모두 체크해  같은 안전영역을 중복해서 발견하지 않도록 하고 다른 안전 영역을 찾는다.

 

코드

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

int n;
int board[100][100];
int visited[100][100];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void dfsSlove(int x, int y, int rain)
{
	//해당 지역을 체크
	visited[x][y] = 1;

	//인접 한 부분의 같은 안전영역들을 체크한다
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(x + dx_dy[i][0], y + dx_dy[i][1]);

		//범위를 넘어가지 않고, 안전영역이고, 체크되지 않았을때
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] > rain &&visited[there.first][there.second] == 0)
		{
			dfsSlove(there.first, there.second, rain);
		}
	}

	
}

//rain만큼의 비가 왔을때 안전 영역의 개수를 구한다
int Solve(int rain)
{
	memset(visited, 0, sizeof(visited));
	
	int ret = 0;

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			//안전 영역을 발견한 경우
			if (board[i][j] > rain && visited[i][j] == 0)
			{
				ret++;

				//해당 안전 영역에 포함된 지역들을 체크해서 같은 안전영역을 중복해서 발견하지 않도록한다
				dfsSlove(i, j, rain);
			}
		}

	return ret;
}

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

	int temp;
	int min_input = 987654321;
	int max_input = -987654321;
	int result = 0;

	cin >> n;

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> temp;
			min_input = min(min_input, temp); //가장 낮은 높이를 구한다
			max_input = max(max_input, temp); //가장 높은 높이를 구한다
			board[i][j] = temp; 
		}

	//물에 잠기지 않을 경우 부터, 모두 물에 잠기기 직전까지 고려하여
	//안전 영역의 개수가 가장 많은 경우의 안전 영역의 개수를 구한다
	for (int i = min_input-1; i < max_input; i++)
	{
		result = max(result, Solve(i));
	}

	cout << result;

	return 0;
}