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

문제링크 : https://www.acmicpc.net/problem/2468

 

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

int arr[102][102];
bool check[102][102];
int n,cnt, mh=-1;
int result = 0;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<pair<int, int>>q;

void bfs(int x, int y)
{
	check[x][y] = 1;
	q.push({ x,y });

	while (!q.empty())
	{
		int xx = q.front().first, yy = q.front().second; q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = xx + dx[i];      //다음 x 값
			int ny = yy + dy[i];      //다음 y 값
			if (nx < 0 || ny < 0 || nx >=n || ny >=n) { continue; }  //범위 조건
			if (check[nx][ny] == 0)   //다음 좌표가 잠기지 않았음
			{
				check[nx][ny] = 1;    //탐색했으므로 방문 처리(잠겼음으로 처리)
				q.push({ nx,ny });
			}
		}
	}	
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] > mh) { mh = arr[i][j]; } //최대 높이 설정
		}
	}

	for (int k = 0; k < mh; k++)  
	{
		cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (arr[i][j] <= k) { check[i][j] = 1; }  //잠겼으면 1
				else { check[i][j] = 0; }                 //잠기지 않았으면 0
			}
		}

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (check[i][j] == 0)  //잠기지 않았으므로 bfs 시작
				{
					bfs(i, j);
					cnt++;
				}
			}
		}

		result = max(result, cnt);
	}
	cout << result;
	return 0;
}

잠긴 구역을 방문 처리을 배열에서 같은 값으로 처리했다. (잠겼으면 1 == 방문했으면 1)

잠기지 않은 구역에서 시작하여 bfs탐색을 돌아서 구역을 확인후 카운트(구역 갯수) 증가시킨다.