백준 2468_안전 영역(C++)

 

www.acmicpc.net/problem/2468

2468번: 안전 영역

[문제 풀이]

BFS를 이용하여 문제를 풀었습니다.

 

이 문제는 물이 0부터 무한대 높이의 비가 내렸을 때, 상, 하, 좌, 우로 서로 연결된 안전 영역의 최대 개수를 구하는 문제입니다. 안전 영역이란 문제 예제에서 높이가 4인 비가 내렸을 때 (0, 0), (0, 1)의 땅은 침수당하지 않습니다. 따라서, 강수량이 4인 경우 좌표 두 개를 묶어 {(0, 0,), (0, 1)} = 안전 영역 하나가 되는 것입니다. 

문제 이해가 끝나셨다면 코드 구현은 어렵지 않습니다. 최소 0부터 최대 = 모두 침수 되는 경우(지역의 최고 높이)까지 반복을 해주시며 BFS를 이용하여 영역 개수만 세우주시면 됩니다.

 

코드 설명은 일반 BFS를 짜는 것과 유사함으로 생략하겠습니다.

[코드]

#include<iostream>
#include<queue>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;  cin >> N;

	int map[101][101];

	int max_hight = 0;

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

			if (max_hight < map[i][j])
				max_hight = map[i][j];

		}
	}

	int answer = 0;

	for (int test = 0; test <= max_hight; test++) {

		int visit[101][101] = { 0, };
		queue<pair<int, int>> safe_map;

		int cnt = 0;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (visit[i][j] == 0 && map[i][j] > test) {

					visit[i][j] = 1;
					cnt++;
					safe_map.push(make_pair(i, j));

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

					while (!safe_map.empty()) {

						int x = safe_map.front().first;
						int y = safe_map.front().second;
						safe_map.pop();

						for (int i = 0; i < 4; i++) {

							int nx = x + dx[i];
							int ny = y + dy[i];

							if (nx < 0 || ny < 0 || nx >= N || ny >= N || visit[nx][ny] == 1 || map[nx][ny] <= test)
								continue;

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

						}

					}
				}

		if (answer < cnt)
			answer = cnt;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				visit[i][j] = 0;
	}

	cout << answer << endl;
	
	return 0;

}