백준 2638번 치즈

문제

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

코드

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

using namespace std;


int N, M;
int dir[4][2] = { {0,1}, {0,-1},{1,0},{-1,0} };

vector<vector<int>> bfs(vector<vector<int>> temp) {
	queue<pair<int, int>> q;
	q.push({ 0,0 });

	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int newY = y + dir[i][0];
			int newX = x + dir[i][1];

			if (newX < 0 || newX >= M || newY < 0 || newY >= N || temp[newY][newX] !=0)continue;

			temp[newY][newX] = 2;
			q.push({ newY,newX });
		}
		
	}
	
	return temp;
}
int main() {
	int answer = 0;
	cin >> N >> M;
	vector<vector<int>> temp(N, vector<int>(M, 0));
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			cin >> temp[i][j];
	}
	

	while (1) {
		vector<vector<int>> copy=temp;
		bool r = false;
		vector<vector<int>> board=bfs(temp);
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 1) {
					r = true;
					int cnt = 0;
					for (int k = 0; k < 4; k++) {
						if (board[i + dir[k][0]][j + dir[k][1]] == 2) {
							cnt++;
						}
					}
					if (cnt >= 2) {
						copy[i][j] = 0;
					}
				}
			}
				
		}
		if (!r) {
			break;
		}
		temp = copy;
		answer++;
	}
	cout << answer;
}

풀이

문제에 써있는 조건대로 구현해주면 되는데

요 조건때문에 저는 바깥 부분을 bfs로 2로 표현했습니다 위의 그림2와 같은 경우에 board는

이렇게 값을 넣어놓고 이중for문을 돌면서 board의 값이 1인것중에 둘러쌓인 4면중 2면 이상이 2값인 값을 지워가면서 풀었습니다~~