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

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

2638번: 치즈

 

[필자 사고]

BFS 탐색 문제다. 

 

이 문제의 핵심 풀이는 외부 공간과 치즈 내부 공간을 구별해야 된다. 

 

인덱스 0,0은 확정적인 외부공간이므로 BFS탐색을 이용해 외부 공간을 방문처리를 해준다.

 

다음으로 치즈가 있는 곳에서 외부공간과 접촉한 갯수가 2개 이상인 경우 배열을 변경해주면 풀이는 완성이다.

 

[소스코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int N, M;
typedef pair<int, int> Node;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
vector<vector<pair<int, int>>> Arr;
vector<vector<bool>> visited;

void InitVisit() {
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M, 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++) {
			int num;
			cin >> num;
			Arr[i][k].first = num;
			Arr[i][k].second = 0;
		}
	}
}
//외부와 내부 구역 나누기
void distintiveOut() {
	InitVisit();
	queue<Node> myQueue;
	myQueue.push({ 0,0 });
	visited[0][0] = 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].first == 0) {
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
			}
		}
	}
}


void SearchAndDelete() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k].first == 1) {
				int count = 0;
				for (int j = 0; j < 4; j++) {
					int nextSero = i + dy[j];
					int nextGaro = k + dx[j];
					if (Inside(nextSero, nextGaro) &&
						visited[nextSero][nextGaro] == true &&
						Arr[nextSero][nextGaro].first == 0) {
						count++;
					}
				}
				Arr[i][k].second = count;

			}

		}
	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k].second >= 2) {
				Arr[i][k].first = 0;
				
				count++;
			}
			Arr[i][k].second = 0;
		}
	}
	

}

bool checkArr() {
	
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k].first == 1) {
				return false;
			}
			

		}
	}
	return true;
}

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

		}
		cout << '\n';
	}
	cout << '\n';
}

int main(void) {
	Input();
	int count = 0;
	while (1) {
		
		if (checkArr() ==true) {
			cout << count;
			return 0;
		}
		distintiveOut();
		SearchAndDelete();
		
		count++;
	}
}