minjgziii

📍 문제

📍 풀이

BFS 활용

- 각 지역의 높이를 입력 받으면서 가장 높은 지역의 값을 maxHeight 변수에 저장해 놓는다. (가장 높은 지역의 높이보다 큰 비가 내리면 어차피 다 잠기기 때문에 똑같기 때문에 maxHeight까지만 반복하면 됨)

- x = 0 (*이때, x = 1부터 돌게 되면 틀린다!! 이거 때문에 계속 틀림)부터 앞에서 구한 maxHeight 까지 반복하면서 BFS를 돌린다. 이때 당연히 아직 방문하지 않았고, 안전한 구역인 곳만 BFS를 실행한다. (안전한 구역 => 현재 x 값보다 큰 구역) 

*x = 0로 돌릴 때 틀리는 이유는 문제에 나와있는 이 조건 때문인 듯하다.

📍 코드

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

int N;
int arr[101][101];
bool visited[101][101];
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };

void BFS(int i,int j, int bound) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	visited[i][j] = true;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i{ 0 }; i < 4; i++) {
			int nowX = x + xDir[i];
			int nowY = y + yDir[i];

			if (nowX < 0 || nowY < 0 || nowX >= N || nowY >= N) {
				continue;
			}
			if (visited[nowX][nowY]) {
				continue;
			}
			// 물에 잠긴 경우 (bound이하)
			if (arr[nowX][nowY] <= bound) {
				continue;
			}

			q.push({ nowX,nowY });
			visited[nowX][nowY] = true;
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	int maxHeight = -1;
	int max = 0;

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

	for (int x{ 0 }; x <= maxHeight; x++) {
		memset(visited, false, sizeof(visited));
		int ans = 0;

		for (int i{ 0 }; i < N; i++) {
			for (int j{ 0 }; j < N; j++) {
				// 방문하지 않았고 안전한 구역
				if (!visited[i][j] && arr[i][j] > x) {
					BFS(i, j, x);
					ans++;
				}
			}
		}

		if (max < ans) {
			max = ans;
		}
	}

	cout << max;
}