백준 2638 치즈

1. 문제 링크

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

2638번: 치즈

 

2.  풀이

1. 비어있는 곳을 탐색하도록 BFS를 수행하면서 치즈를 만날 때마다 그 위치에 카운트를 1 증가시킨다.
2. 카운트를 증가시킬 때 마다 해당 위치의 누적 카운트를 측정해 2 이상이면 그 위치는 다음 턴에 제거될 위치로 선정한다.
3. 제거될 위치에 있는 치즈를 제거 후 그 위치부터 다시 1번 과정을 반복한다. 

#include <iostream>
#include <queue>

using namespace std;

class Pos {
public:
	int r, c;
	Pos() {};
	Pos(int r, int c) {
		this->r = r;
		this->c = c;
	};

};

int					N, M;
int					board[100][100];
bool				visited[100][100];
int					cntBoard[100][100];
queue<Pos>			nextRemoveChessQ;

const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };

void InputAndInit() {
	while (!nextRemoveChessQ.empty())
		nextRemoveChessQ.pop();
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			visited[i][j] = false;
			cntBoard[i][j] = 0;
		}
	}
}

bool IsInBoard(const Pos& p) {
	return (p.r >= 0 && p.r < N && p.c >= 0 && p.c < M);
}

void BFS(Pos startP) {
	queue<Pos> q;
	q.push(startP);
	visited[startP.r][startP.c] = true;

	while (!q.empty()) {
		Pos currentP = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			Pos nextP = { currentP.r + dr[i],currentP.c + dc[i] };
			if (!IsInBoard(nextP) || visited[nextP.r][nextP.c])
				continue; // board를 벗어나거나 이미 방문된 지점이면 넘어감
			
			if (board[nextP.r][nextP.c] == 1) {	//치즈가 있는 지점이면
				cntBoard[nextP.r][nextP.c]++;
				if (cntBoard[nextP.r][nextP.c] >= 2) 
					nextRemoveChessQ.push(nextP);
				continue;
			}
			q.push(nextP);
			visited[nextP.r][nextP.c] = true;	
		}
	}
}

int GetMeltingTime() {
	int time = 0;
	nextRemoveChessQ.push({ 0,0 });
	while (!nextRemoveChessQ.empty()) {
		time++;
		int len = nextRemoveChessQ.size();

		for (int i = 0; i < len; i++) {
			Pos removedP = nextRemoveChessQ.front(); nextRemoveChessQ.pop();
			board[removedP.r][removedP.c] = 0;
			cntBoard[removedP.r][removedP.c] = 0;
			nextRemoveChessQ.push(removedP);
		}

		for (int i = 0; i < len; i++) {
			Pos removedP = nextRemoveChessQ.front(); nextRemoveChessQ.pop();
			if (!visited[removedP.r][removedP.c])
				BFS(removedP);
		}
	}

	return time - 1;
}

int main() {
	InputAndInit();
	cout << GetMeltingTime() << "\n";
}