백준 2573 c++ "빙산" -[PlusUltraCode]

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

2573번: 빙산

[필자 사고]

이 문제는 BFS탐색 알고리즘을 사용하여 풀 수 있는 문제이다.

 

이 문제의 특이한 점은 빙하가 녹는 점을 굳이 BFS탐색이 아닌 완전 탐색으로 구현 가능하다는 점이다.

 

구현하는데 다소 어려울 수 있는 문제이다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> Node;
vector<vector<int>> Arr;
int N, M;
void Print() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cout << Arr[i][k] << " ";
		}
		cout << '\n';
	}
}
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int bingSero = 0;
int bingGaro = 0;
bool binaryCheck = false;
bool finshCheck = false;
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

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

}

void Minus_Water() {
	vector<vector<int>> Count;
	Count.resize(N);
	for (int i = 0; i < N; i++) {
		Count[i].resize(M, 0);
	}


	for (int nowSero = 0; nowSero < N; nowSero++) {
		for (int nowGaro = 0; nowGaro < M; nowGaro++) {
			if (Arr[nowSero][nowGaro] != 0)continue;
			for (int i = 0; i < 4; i++) {
				int nextSero = nowSero + dy[i];
				int nextGaro = nowGaro + dx[i];
				if (Inside(nextSero, nextGaro) &&
					Arr[nextSero][nextGaro] > 0) {
					Count[nextSero][nextGaro]++;
				}
			}
		}
	}

	
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			Arr[i][k] -= Count[i][k];
			if (Arr[i][k] < 0)Arr[i][k] = 0;
			if (Arr[i][k] > 0) {
				bingSero = i;
				bingGaro = k;
			}
		}
	}
	
}

void BFS() {
	queue<Node> myQueue;
	vector<vector<bool>> visited;
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M, false);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k] == 0) {
				visited[i][k] = true;
			}
		}
	}
	myQueue.push({bingSero,bingGaro });
	
	visited[bingSero][bingGaro] = 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) &&
				visited[nextSero][nextGaro] == false &&
				Arr[nextSero][nextGaro] != 0) {
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
			}
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (visited[i][k] == false&&Arr[i][k]>0) {
				
				binaryCheck = true;
				return;
			}
		}
	}
}



int main(void) {
	Input();
	int Count = 0;
	while (binaryCheck != true) {
		
		Minus_Water();
		if (Arr[bingSero][bingGaro] == 0) {
			cout << 0;
			return 0;
		}
		BFS();
		Count += 1;
	}
	cout << Count;

}