백준 2638번 치즈

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

2638번: 치즈

 

 

 

 

<접근방법>

탐색 문제입니다.

그런데 문제가 있습니다.

내부 공기, 외부 공기의 개념이 존재한다는 것입니다.

 

내부 공기의 특징을 보면 치즈로 둘러쌓여 있습니다.

즉, 외부 공기에서 bfs를 돌렸을 때 서로 만나지 않습니다.

 

그렇다면 외부 공기에서 bfs 돌리고 각 치즈를 몇 번 접촉하였는지 저장하여

녹는 처리를 해주면 됩니다.

마침 치즈의 가장자리는 항상 비어있으니(문제 조건) 구현이 매우 편하겠군요.

 

접촉 횟수 저장을 cnt 배열을 따로 만들어서 처리하였습니다.

 

 

---

 

 

 

<코드>

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

struct point {
	int y, x;
};

int n, m, map[101][101];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int cnt[101][101];

bool bfs(int y, int x) {
	queue<point>q;
	bool visit[100][100] = {false, };

	q.push({y, x});
	visit[y][x] = true;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
			if (visit[ty][tx]) continue;

			if (map[ty][tx] == 1) cnt[ty][tx]++;

			if (map[ty][tx] == 0){
				q.push({ty, tx});
				visit[ty][tx] = true;
			}
		}
	}
	bool flag = false;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (cnt[i][j] >= 2) {
				map[i][j]--;
				flag = true;
			}
		}
	}

	return flag;
}

void simul() {
	int time = 0;
	while (bfs(0, 0)) {
		memset(cnt, 0, sizeof(cnt));
		time++;
	}
	cout << time << '\n';
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	simul();

	return 0;
}

 

 

---

 

 

<느낀 점>