[c++/백준] 2638번: 치즈

문제 링크

2638번: 치즈

풀이

BFS 응용 문제
코드 짜면서 시간초과 날 것 같은데... 했는데 안남!

1. 모눈종이의 가장자리는 치즈가 놓이지 않는다고 했고, 외부공기의 체크를 위해 bfs(0,0)으로 외부 공기를 체크해준다. 여느 BFS 문제와 같이 queue를 이용하면 된다.
   1-1. 이를 통해 외부 공기는 visit 벡터에 1로 표현 되어 있을 것이다.
2. 외부 공기를 체크하는 queue의 반복문이 끝나면 외부 공기와 맞닿은 치즈들을 녹일 차례
   2-1. arr[i][j]가 1이면 치즈인데 치즈의 상하좌우 visit이 1인게 2개 이상이면 외부 공기와 맞닿은 치즈라는 의미가 되므로 arr[i][j]=0으로 치즈를 녹여준다.
3. 1번,2번 과정이 치즈를 녹이는 한 세트이므로 ans++를 해준다.
4. visit을 clear해주는데, 그 이유는 또 다시 bfs(0,0)를 돌려 외부 공기 체크 및 치즈를 녹여야 하기 때문이다.
5. 1~4번의 과정을 치즈가 모두 녹을 때까지 실행하고 ans를 출력한다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int ans = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
vector<vector<int>> arr;
vector<vector<int>> visit;
queue<pair<int,int>> q;

void bfs(int y, int x) {
	q.push({ y,x });
	visit[y][x] = 1;
	while (!q.empty()) { //외부공기체크
		int ny = q.front().first;
		int nx = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			if (ny + dy[i]<0 || ny + dy[i]>=n || nx + dx[i]<0 || nx + dx[i]>=m) continue; //범위 밖이면 
			if (visit[ny + dy[i]][nx + dx[i]] == 1) continue; //방문했으면
			if (arr[ny + dy[i]][nx + dx[i]] == 0) { //공기라면
				visit[ny + dy[i]][nx + dx[i]] = 1;
				q.push({ ny + dy[i],nx + dx[i] });
			}
		}
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (arr[i][j] == 1) {
				int chk = 0;
				for (int k = 0;k < 4;k++) {
					if (dy[k] + i < 0 || dy[k] + i >= n || dx[k] + j < 0 || dx[k] + j >= m) continue;
					if (visit[dy[k] + i][dx[k] + j] == 1) chk++;
				}
				if (chk >= 2) {
					arr[i][j] = 0;
				}
			}
		}
	}
	ans++;
	visit.clear();
	visit.resize(n, vector<int>(m));
}

int main()
{
	cin >> n >> m;

	arr.resize(n, vector<int>(m));
	visit.resize(n, vector<int>(m));

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

	while (1) {
		int flag = 0;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < m;j++) {
				if (arr[i][j] == 1) {
					flag = 1;
					break;
				}
			}
			if (flag == 1) break;
		}
		if (flag == 1) bfs(0, 0);
		else break;
	}

	cout <<ans;

	return 0;
}