백준 2636 c++ "치즈" -[PlusUltraCode]

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

2636번: 치즈

[필자 사고]

이 문제는 BFS탐색 알고리즘을 사용하면 해결할 수 있는 문제이다.

 

특이한 점은 치즈의 안과 밖을 구분해야 된다는 점이다.

 

처음에는  2번의 BFS를 이용하여 안과 밖을 구분하겠다 생각 했지만 1번의 BFS만으로 안과 밖을 구분할 수 있던걸 깨닫고 코드로 만들었다.

 

[소스 코드]

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

typedef struct Cheeze {
	int isCheeze; //1은 치즈 0은 빈공간
	int jari; // 0은 외부 1은 외부아님 
	bool Delete;

}Cheeze;
typedef pair<int, int> Node;
int N, M;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}


vector<vector<Cheeze>> Arr;

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++) {
			int num;
			cin >> num;
			Arr[i][k].isCheeze = num;
			Arr[i][k].jari = -1;
			Arr[i][k].Delete = false;
		}
	}
}
vector<vector<bool>> visited;

void BFS() {
	queue<Node> myQueue;
	myQueue.push({ 0,0 });
	visited[0][0] = true;
	Arr[0][0].jari = 0;
	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) == false)continue;
			if (visited[nextSero][nextGaro] == true)continue;
			if (Arr[nextSero][nextGaro].isCheeze == 0) {
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
				Arr[nextSero][nextGaro].jari = 0;
			}
			else if (Arr[nextSero][nextGaro].isCheeze == 1) {
				Arr[nextSero][nextGaro].jari = 1;
				Arr[nextSero][nextGaro].Delete = true;
			}
		}
	}
}

int CountCheeze() {
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k].isCheeze == 1) {
				count++;
			}
		}
	}
	return count;
}
void DeleteCheeze() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k].Delete==true) {
				Arr[i][k].isCheeze = 0;
				Arr[i][k].jari = -1;
				
			}

		}
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			Arr[i][k].jari = -1;
				
			

		}
	}
}
void Print() {
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cout << Arr[i][k].isCheeze << " ";

		}
		cout << '\n';
	}
}
bool gameOver = false;
int ResultPrevCount = -1;
void MakeCheezeArr() {
	int prevCount = CountCheeze();
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M, false);
	}
	BFS();
	DeleteCheeze();
	int nowCount = CountCheeze();
	if (nowCount == 0) {
		ResultPrevCount = prevCount;
		gameOver = true;
		return;
	}
	


	
}


int main(void) {

	Input();
	int time = 0;
	while (1) {
		MakeCheezeArr();
		
		time++;
		if (gameOver == true) {
			cout << time << '\n';
			cout << ResultPrevCount;
			return 0;
		}
	}
}