[2468번] 안전 영역

www.acmicpc.net/problem/2468

2468번: 안전 영역

풀이

이 문제는 플러드 필의 유형이지만, 물에 잠기는 높이에 따라 영역이 달라진다는 차별점이 있습니다.

저는 지점의 높이를 입력받을 때 최저 높이와 최대 높이를 미리 변수에 저장해두었습니다.

그리고 for문을 통해 min_num ~ max_num까지 순회하며 bfs하는 횟수를 계산하였습니다.

int min_num = 101; // 최저 높이
int max_num = 0; // 최대 높이

for (int i = 0;i < n;i++) {
	for (int j = 0;j < n;j++) {
		cin >> arr[i][j];
		min_num = min(min_num, arr[i][j]);
		max_num = max(max_num, arr[i][j]);
	}
}

 

bfs 코드입니다.

int x_[4] = { 0,0,1,-1 };
int y_[4] = { 1,-1,0,0 };

void bfs(int y, int x, int safe_max) {
	q.push({ y,x });
	check[y][x] = true;
	while (!q.empty()) {
		int node_y = q.front().first;
		int node_x = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int next_y = node_y + y_[i];
			int next_x = node_x + x_[i];
			if (next_y >= n || next_y < 0 || next_x >= n || next_x < 0) continue;
			if (check[next_y][next_x]) continue;
			if (arr[next_y][next_x] > safe_max) {
				check[next_y][next_x] = true;
				q.push({ next_y,next_x });
			}
		}
	}
}

인자로 물에 잠기는 높이를 받아와, 그 높이보다 지점의 높이가 높은 경우에만 queue에 집어넣게 하였습니다.

전체 코드

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

typedef long long ll;

int check[101][101];
int arr[101][101];
queue<pair<int, int>> q;

int n;

int x_[4] = { 0,0,1,-1 };
int y_[4] = { 1,-1,0,0 };

void bfs(int y, int x, int safe_max) {
	q.push({ y,x });
	check[y][x] = true;
	while (!q.empty()) {
		int node_y = q.front().first;
		int node_x = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int next_y = node_y + y_[i];
			int next_x = node_x + x_[i];
			if (next_y >= n || next_y < 0 || next_x >= n || next_x < 0) continue;
			if (check[next_y][next_x]) continue;
			if (arr[next_y][next_x] > safe_max) {
				check[next_y][next_x] = true;
				q.push({ next_y,next_x });
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); std::cout.tie(0);

	cin >> n;

	int min_num = 101;
	int max_num = 0;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> arr[i][j];
			min_num = min(min_num, arr[i][j]);
			max_num = max(max_num, arr[i][j]);
		}
	}

	int res = 1;
	for (int i = min_num;i <= max_num;i++) {

		int tmp = 0;
		for (int j = 0;j < n;j++) {
			for (int k = 0;k < n;k++) {
				if (!check[j][k] && arr[j][k] > i) {
					bfs(j, k, i);
					tmp++;
				}
			}
		}

		res = max(res, tmp);

		memset(check, false, sizeof(check));
	}

	std::cout << res << "\n";

	return 0;
}