[BOJ 2638 // C++] 치즈

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2638번 문제인 치즈이다.
문제는 아래 링크를 확인하자.

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

2638번: 치즈

치즈는 바깥과 연결된 부분만 녹을 수 있다는 점에 주목하자.

여러번의 bfs 시뮬레이션으로 "바깥에서 접근할 수 있는 녹는 치즈"들을 찾아낸 뒤 한번에 녹이는 것을 반복하는 것으로 이 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

bool cheese[100][100];
int need[100][100];
int melting[100][100];
int visited[100][100];

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

bool chk(int R, int C) {
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (cheese[r][c]) return 1;
		}
	}
	return 0;
}

queue<pair<int, int>> que;

void bfs(int R, int C) {
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (visited[rr][cc]) continue;
			if (cheese[rr][cc]) {
				need[rr][cc]--;
				if (need[rr][cc] == 0) melting[rr][cc] = 1;
			}
			else {
				visited[rr][cc] = 1;
				que.push({ rr,cc });
			}
		}
	}
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (melting[r][c]) cheese[r][c] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C; cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> cheese[r][c];
		}
	}

	int ans = 0;
	while (chk(R, C)) { // 안 녹은 치즈가 있는 동안
		memset(melting, 0, sizeof(melting));
		memset(visited, 0, sizeof(visited));
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (cheese[r][c]) need[r][c] = 2;
				else need[r][c] = 0;
			}
		}
		que.push({ 0,0 });
		visited[0][0] = 1;
		bfs(R, C);
		ans++;
	}

	cout << ans;
}