백준 2636 - 치즈

문제링크

• 백준 2636

문제설명

• NxM 크기의 보드에 치즈가 놓인 곳(1), 공기가 놓인 곳(0)이 있다.
• 치즈로 인해 고립된 공기 영역은 치즈가 녹는데 영향을 주지 않고, 고립되지 않은 공기 영역과 맞닿은 치즈는 한시간 뒤에 녹는다.
• 모든 치즈가 녹기까지 걸리는 시간과, 녹기 한시간 전의 존재하던 치즈 개수를 구하라

문제접근

• 보드의 테두리 부분은 항상 공기가 존재하는 부분이므로, (0,0)에서 공기가 존재하는 칸에 대한 BFS를 적용한다. 이때, 방문하지 못한 공기 영역은 치즈를 녹이는데 영향을 주지 않는 영역이다.
  • BFS로 접근되는 공기가 들어있는 칸은 -1로 표시한다.
• 치즈가 놓인 칸에 대해서 BFS를 적용해서 공기(-1)와 맞닿은 치즈들을 모두 2로 표시한다.
• 녹는 치즈(2)를 모두 0으로 바꾸고, 공기들의 상태도 모두 0으로 재설정해준다.
• 위 과정을 남은 치즈의 개수가 0이 될때까지 반복한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

int N, M;
// -1: 영향력 있는 공기, 0: 영향력 없는 공기, 1:녹지 않는 치즈, 2:녹는 치즈
int board[100][100]; 
bool visited[100][100];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans = 0;

void airBfs(int xpos, int ypos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xpos, ypos));
	board[xpos][ypos] = -1;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY<0 || nextY>=M) continue;
			if (board[nextX][nextY] != 0) continue;
			board[nextX][nextY] = -1;
			q.push(make_pair(nextX, nextY));
		}
	}
}

void cheeseBfs(int xpos, int ypos) {
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push(make_pair(xpos, ypos));
	visited[xpos][ypos] = true;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		// 녹는 치즈 설정 & 다음 탐색할 치즈 담기
		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
			if (board[nextX][nextY] == -1) board[cpos.first][cpos.second] = 2; // 녹는 치즈
			if (board[nextX][nextY] == 1) {
				if (visited[nextX][nextY]) continue;
				visited[nextX][nextY] = true;
				q.push(make_pair(nextX, nextY));
			}
		
		}
	}
}

int getCheeseCount() {
	int cnt = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++)
			if (board[r][c] == 1) cnt++;
	}
	if (cnt != 0) ans = cnt;
	return cnt;
}

void meltCheese() {
	int time = 0;
	while (true) {
		if (getCheeseCount() == 0) break;
		airBfs(0, 0);
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (board[r][c] == 1) {
					cheeseBfs(r, c);
				}
			}
		}
		// melt cheese
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (board[r][c] == 2) board[r][c] = 0;
				if (board[r][c] == -1) board[r][c] = 0; // reset air area
			}
		}
		time++;
	}
	printf("%d\n%d\n", time, ans);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &board[r][c]);
		}
	}
	meltCheese();

}