[BOJ] 백준 2636 치즈 c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/2636 

2636번: 치즈

---

풀이

껍질부터 하나씩 찾아가야 하는 문제이다.

이 문제의 핵심은 아래 부분이다.

판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며

 

즉, 가장자리는 치즈가 없으므로, 치즈의 바깥부분 (0, 0)부터 bfs로 탐색을 하면 된다.

 

BFS

바깥 부분에서 공기(0)을 만나면, 큐에 추가한 후, 방문 표시를 해준다.

치즈(1)을 만나면, 녹아 없어지므로 공기(0)으로 바꿔주고, 방문 표시를 해준다

if(arr[nrow][ncol] == 0) {
    check[nrow][ncol] = true;
    q.push({nrow, ncol});
}
else {
    check[nrow][ncol] = true;
    arr[nrow][ncol] = 0;
    melt_cnt++;
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int arr[100][100];
bool check[100][100];
int N, M;
int time_cnt, last_cnt;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool bfs() {
	time_cnt++;
	queue<pair<int, int>> q;
	q.push({0, 0});
	int melt_cnt = 0;

	while (!q.empty()){
		int row = q.front().first;
		int col = q.front().second;
		q.pop();
		check[row][col] = true;

		for(int i = 0; i < 4; i++) {
			int nrow = row + dy[i];
			int ncol = col + dx[i];

			if(nrow < 0 || nrow >= N || ncol < 0 || ncol >= M || check[nrow][ncol]) continue;

			if(arr[nrow][ncol] == 0) {
				check[nrow][ncol] = true;
				q.push({nrow, ncol});
			}
			else {
				check[nrow][ncol] = true;
				arr[nrow][ncol] = 0;
				melt_cnt++;
			}
		}
	}
	if(!melt_cnt) return true;
	else {
		last_cnt = melt_cnt;
		return false;
	}
}


int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	while(true) {
		if(bfs()) break;
		memset(check, 0, sizeof(check));
	}

	cout << --time_cnt << '\n' << last_cnt << '\n';

	return 0;
}