백준 2468 : 안전 영역

1. 문제 : https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

2. 문제 접근

• 장마로 인한 물의 높이가 얼마인지 주어지지 않았으며, 안전지대의 개수는 지역의 높이에 따라 규칙 없이 달라짐. -> 최소 높이인 $0$부터 지역의 최대 높이인 $100$까지 모두 확인해야 함 -> 완전 탐색
• 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS 사용

 

3. 문제 해결

1. 높이 $h$를 $0$부터 $100$까지 설정하고 안전 지대 개수를 확인
2. 주어진 이차원 배열을 BFS를 활용하여 안전 지대의 개수 계산
3. 해당 갯수가 최대 개수인지 확인하고 모든 높이를 검사한 후 최댓값 반환

 

4. 코드

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

int solution(int N, vector<vector<int>>& map)
{
	int answer = 0;

	int dx[4] = { 0, 0, -1, 1 };
	int dy[4] = { 1, -1, 0, 0 };
	vector<vector<bool>> visited;

	// Initialize the matrix for checking whether the node is visited
	for (int i = 0; i < N; i++)
	{
		vector<bool> temp;
		for (int j = 0; j < N; j++)
		{
			temp.push_back(false);
		}
		visited.push_back(temp);
	}

	// Find the max number of safety zone
	for (int h = 0; h <= 100; h++)
	{
		// Initialize the matrix value
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				visited[i][j] = false;
			}
		}

		// Search the map
		int num = 0;
		queue<pair<int, int>> bfs;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (map[i][j] <= h) continue;
				if (visited[i][j]) continue;

				// Calculate the area of the safety zone
				bfs.push({ i, j });
				while (!bfs.empty())
				{
					pair<int, int> pos = bfs.front();
					bfs.pop();

					int x = pos.first, y = pos.second;
					for (int i = 0; i < 4; i++)
					{
						int tx = x + dx[i], ty = y + dy[i];
						// Out of range, already flooded, already visited
						if (tx < 0 || ty < 0 || tx >= N || ty >= N || map[tx][ty] <= h || visited[tx][ty]) continue;

						bfs.push({ tx, ty });
						visited[tx][ty] = true;
					}
				}

				num++;
			}
		}

		// Check the max number of safety zone
		if (answer < num)
		{
			answer = num;
		}
	}

	return answer;
}

int main()
{
	int N;
	vector<vector<int>> map;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		vector<int> temp;

		for (int j = 0; j < N; j++)
		{
			int h;
			cin >> h;
			temp.push_back(h);
		}

		map.push_back(temp);
	}

	cout << solution(N, map);

	return 0;
}