백준 2638 치즈

문제링크

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

문제

키포인트

• 가장자리는 치즈가 놓이지 않으므로 가장자리에서 부터 BFS나 DFS를 실행해줍니다. (아래 코드는 bfs 이용)
• 0인 부분(치즈가 없는 영역)은 방문하지 않았다면 큐에 넣어주고 1인 부분(치즈가 있는 영역) 은 큐에 넣지 않고 해당 좌표의 값을 1증가 시켜줍니다.
• 큐가 빌때까지 bfs를 실행 후 maps에서 좌표의 크기가 3이상인 좌표의 값들은 0으로 초기화 시켜줍니다. (1 + 닿은 횟수 2)
• 이 작업을 반복하며 몇번 실행했을때 치즈가 완전히 없어지는지 카운트 하여 정답을 알아낼 수 있습니다.

시행착오

비슷한 유형의 문제를 여러번 풀어봐서 크게 고민하지는 않았습니다.

코드

#include <iostream>
#include <queue>
using namespace std;
int n, m;
int maps[101][101];
bool vi[101][101];
queue<pair<int, int>> q;
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };
bool solve() {
	fill(&vi[0][0], &vi[100][101], false);
	q.push({ 0,0 });
	vi[0][0] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (maps[nx][ny] >= 1) maps[nx][ny]++;
			else {
				if (!vi[nx][ny]) {
					vi[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}
	
	bool check = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] >= 3) {
				maps[i][j] = 0;
				check = true;
			}
			if (maps[i][j] >= 1) {
				maps[i][j] = 1;
			}
		}
	}

	return check;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
		}
	}

	int cnt = 0;
	while (solve()) cnt++;
	cout << cnt;
}

후기

무난한 bfs dfs 문제였습니다.