백준 2468 c++ - [PlusUltraCode]

[필자 사고]

이 문제는 전형적인 2차원 배열 탐색문제이다

 

특이한 점은 물에 잠겨있는 안정 지역의 최댓값을 구해야 한다.

 

좀 더 효율적인 방법이 있나 생각을 해봤지만 떠오르지 않았고 

 

입력되는 N의 최댓값이 100이므로 시간복잡도 측면에서 문제가 되지 않아 

 

전체 경우의 수를 다 고려해주기로 했다.

 

물의 높이를 0부터 최대까지 다 고려해 BFS알고리즘을 수행했다.

 

 

[소스 코드]

 

 

 

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

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

vector<vector<int>> Arr;
vector<vector<bool>> visited;
int N;
int maxNum = -1;
int ResultCnt = -1;
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void BFS(int Water) {
	vector<vector<int>> Temp;
	Temp = Arr;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Temp[i][k] <= Water) {
				Temp[i][k] = -1;
			}
		}
	}
	queue<pair<int, int>>myQueue;
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Temp[i][k] != -1&&visited[i][k]==false) {
				cnt++;
				myQueue.push({ i,k });
				visited[i][k] = true;
				while (!myQueue.empty()) {
					int nowSero = myQueue.front().first;
					int nowGaro = myQueue.front().second;
					myQueue.pop();
					for (int i = 0; i < 4; i++) {
						int nextSero = nowSero + dy[i];
						int nextGaro = nowGaro + dx[i];
						if (Inside(nextSero, nextGaro) &&
							Temp[nextSero][nextGaro] != -1 &&
							visited[nextSero][nextGaro] == false) {
							visited[nextSero][nextGaro] = true;
							myQueue.push({ nextSero,nextGaro });
						}
					}
				}
			}
		}
	}
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N);
	}
	if (ResultCnt < cnt) {
		ResultCnt = cnt;
		return;
	}
	
}

void Input() {
	cin >> N;
	Arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
		visited[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
			if (maxNum < Arr[i][k])maxNum = Arr[i][k];
		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	for (int i = 0; i <= maxNum; i++) {
		BFS(i);
	}
	cout << ResultCnt;
}