[C++][백준] - 안전 영역(2468번)

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

🔔 문제 : 

 

(2<= N <= 100) 인 N*N 의 지도가 있습니다.

 

각각의 구역에는 1 이상 100이하인 높이가 적혀져 있습니다.

 

비가 안오는 0 높이부터 비가 꽉차게 오는 경우까지 경우의 수가 다양하게 오는데

 

이 중 어떤 높이의 비가 오더라도, 안전한 영역의 갯수의 최댓값을 출력하는 문제입니다.

 

예를 들어, 위와같이 비가 6높이로 왔을 때, 안전한 영역은 4개가 됩니다.

 

---

🔔 Kick Point :

시간을 줄이기 위한 조건으로, 높이값을 받을 때, 최댓값을 따로 저장해주었습니다.

 

그 이후, 비가 안오는 경우부터 꽉차게 오는 경우 까지, BFS를 통하여 안전한 영역을 구하였습니다.

---

🔔 Code :

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

// 1~100, 높이  0부터 99까지 물에 다 잠기는 시나리오
// 처음 진입 할 때, 최대값을 가지고 있으면 좋을 듯
// BFS나 DFS를 통하여 섬을 싹다 구하면 될듯?


// variable
int n;
int MAX = 0;

int map[100][100];
bool isVisited[100][100];

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

int BFS(int rain) {
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] <= rain) {
				isVisited[i][j] = true;
			}
		}
	}

	int cnt(0);
	queue<pair<int, int>> q;
	for (int i = 0; i < n * n; i++) {
		int y = i / n; 
		int x = i % n; 

		if (isVisited[y][x]) continue;

		q.push({ y,x });
		isVisited[y][x] = true;

		// 주변 섬 둘러보기
		while (!q.empty()) {
			int _y = q.front().first;
			int _x = q.front().second;
			q.pop();

			for (int j = 0; j < 4; j++) {
				int ny = _y + dy[j];
				int nx = _x + dx[j];

				if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
				if (isVisited[ny][nx]) continue;

				q.push({ ny,nx });
				isVisited[ny][nx] = true;
			}
		}
		cnt++;
	}
	
	return cnt;

}


int main() {
	// Input
	cin >> n;

	int heightMax(0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp; cin >> tmp;
			map[i][j] = tmp;
			heightMax = tmp > heightMax ? tmp : heightMax;
		}
	}

	// Solve
	for (int i = 0; i < heightMax; i++) {
		memset(isVisited, 0, sizeof(isVisited));
		int tmp = BFS(i);
		MAX = MAX < tmp ? tmp : MAX;
	}


	// Output
	cout << MAX;
}

---