백준 2636 치즈

백준 2636

n,m이 최대 100개라 최악의 경우를 고려해도 아마 O(N^2M^2) 정도.. 시간초과 날 일은 없다.

1. 일단 치즈가 바깥치즈인지 확인하는 bfs를 돌리고 그 위치들을 따로 vis1이라는 배열에 기록한다.
2. board에 녹은 치즈를 반영한다.
3. 1,2번을 반복하면서 board에 모든 치즈가 녹을때까지 돌리면 된다.

#include <bits/stdc++.h>
using namespace std;
int vis[101][101];
int vis1[101][101];
int board[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
vector<int> v;
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 >> board[i][j];
		}
	}
	
	int hour = -1;
	while (1) {

		int cnt = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!board[i][j]) continue;
				queue<pair<int, int>> q;
				q.push({ i,j });
				vis[i][j] = 1;
				int flag = 0;

				while (!q.empty()) {
					auto cur = q.front();
					q.pop();

					for (int t = 0; t < 4; t++) {
						int nx = cur.first + dx[t];
						int ny = cur.second + dy[t];

						if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

						if (nx == 0 || ny == 0 || nx == n - 1 || ny == m - 1) {
							vis1[i][j] = 1;
							cnt++;
							flag = 1;
							break;
						}

						if (!board[nx][ny] && !vis[nx][ny]) {
							q.push({ nx,ny });
							vis[nx][ny] = 1;
						}
					}
					if (flag) break;
				}
				memset(vis, 0, sizeof(vis));
			}
		}
		hour++;
		if (cnt == 0) break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] -= vis1[i][j];
			}
		}
		v.push_back(cnt);
		memset(vis1, 0, sizeof(vis1));
		
	}

	cout << hour << '\n' << v[v.size()-1] << '\n';
}