백준 / 바킹독님의 문제집 / 안전 영역(2468)

문제 설명

 

 

문제 해결

 

해당 문제도 BFS를 이용하여 풀었다.

일단 비에 양에 따라 달라지는 안전 지역의 개수를 계산하기 위해서

맵에 입력된 지역의 높이 중, 최대 높이가 얼마인지 구했다.

 

그리고 0부터 시작하여 최대 높이 직전까지 비가 내렸을 때 최대 얼마나 많은 안전 지대가 나오는지 확인했다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <tuple>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <algorithm>

#define x first
#define y second

using namespace std;

int N, max_height = 0;
int map[101][101];

queue<pair<int, int>> q;
pair<int, int> direction[4] = { make_pair(1,0), make_pair(0,1), make_pair(-1,0), make_pair(0,-1) };

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			if (max_height < map[i][j])
				max_height = map[i][j];
		}
	}

	int safe_zone = 0;
	for (int i = 0; i < max_height; i++)
	{
		int visit[101][101] {0};
		int temp = 0;
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N; k++)
			{
				if (visit[j][k] == 0 && map[j][k] > i)
				{
					q.push(make_pair(j, k));
					visit[j][k] = 1;

					while (!q.empty())
					{
						auto current = q.front();
						q.pop();

						for (int p = 0; p < 4; p++)
						{
							int nx = current.x + direction[p].x;
							int ny = current.y + direction[p].y;

							if (nx < 0 || nx >= N || ny < 0 || ny >= N)
								continue;

							if (visit[nx][ny] == 1 || map[nx][ny] <= i)
								continue;

							visit[nx][ny] = 1;
							q.push(make_pair(nx, ny));
						}
					}

					temp++;
				}
			}
		}
		if (safe_zone < temp)
			safe_zone = temp;
	}
	
	cout << safe_zone << '\n';
	return 0;
}

 

문제 해결