[c++/백준] 2469번: 안전 영역

문제 링크

2469번: 안전 영역

풀이

그래프로 푸는 문제. 난 BFS로 풀었다.

1. 먼저 보드를 초기화하면서 제일 높은 높이를 구한다.(max_height)
2. 높이는 0부터 max_height까지 모두 체크하면서 BFS를 호출한다. (모든 높이에서의 영역 개수를 구해야 하니)
   2-1. 보드를 돌리면서 높이가 i보다 높고, 방문하지 않았다면 BFS를 호출한다.
   2-2. 여느 BFS와 같이 queue를 사용한다. 범위와 방문 체크를 하고, 물에 인접한 영역이 물에 안잠긴다면 queue에 push하고 방문 체크를 한다.
   2-3. 한 영역의 체크가 끝나면(BFS함수가 모두 끝나면) return 1;하고 cnt에 더해준다.
3. answer에 각 높이마다 구하던 cnt의 최댓값으로 갱신해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<vector<int>> arr;
vector<vector<int>> visit;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int BFS(int height, int y, int x)
{
	queue<pair<int, int>> q;
	q.push({ y,x });
	visit[y][x] = 1;
	
	while (!q.empty())
	{
		int ty = q.front().first;
		int tx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = ty + dy[i];
			int nx = tx + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
			if (visit[ny][nx] == 1) continue;
			if (arr[ny][nx] > height) // 물에 안 잠기는 영역 체크
			{
				visit[ny][nx] = 1;
				q.push({ ny,nx });
			}
		}
	}

	return 1;
}

int main(void)
{
	cin >> n;
	arr.resize(n, vector<int>(n));
	
	int max_height = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
			max_height = max(max_height, arr[i][j]);
		}
	}

	int answer = 0;
	for (int i = 0; i < max_height; i++) // 높이 i 이하는 잠김
	{
		visit.resize(n, vector<int>(n));
		int cnt = 0;
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (arr[j][k] > i && visit[j][k] == 0)
				{
					cnt += BFS(i, j, k);
				}
			}
		}

		answer = max(answer, cnt);
		visit.clear();
	}

	cout << answer << endl;
	return 0;
}