#2638 치즈

문제를 풀기전에 알고리즘 설계를 다음과 같이 했습니다.
빈칸과 2개 이상 접촉해 있다면 치즈를 녹인다
만일 내부 공기라면 치즈에 영향을 주지 않는다.
알고리즘 순서
1. 초기 외부 공기 설정

bfs 함수의 visit 배열을 전역변수로 설정하여서 방문처리가 돼 있지 않은 visit들로만 참조를 하였습니다.
따라서 매 턴마다 100*100범위 안에서 visit처리가 돼 있지 않은 값들만 고려하게 되어 탐색횟수를 줄일 수 있었습니다.

2. 외부공기와 접촉해 있는 치즈 외부공기로 바꿔주기

3. 내부공기였는데 외부공기와 접촉해 있다면 외부공기로 바꿔준다

2,3 반복

	// #b 2638 치즈
	#include <iostream>
	#include <queue>
	using namespace std;
	#define endl '\n'
	int n, m;
	int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };
	int arr[101][101];
	int visit[101][101];
	typedef struct xy {
	int x, y;
	}xy;
	void bfs(int x,int y) {
	// 1. 초기 외부 공기 설정
	queue<xy> q;
	q.push({ x,y });
	visit[x][y] = true;
	arr[x][y] = 0;
	while (!q.empty()) {
	int fx = q.front().x;
	int fy = q.front().y;
	q.pop();
	for (int i = 0; i < 4; i++) {
	int nx = fx + dir[i][0];
	int ny = fy + dir[i][1];
	if (nx<0 || nx>n + 1 || ny<0 || ny>m + 1)continue;
	if (visit[nx][ny])continue;
	if (arr[nx][ny] == 1)continue;
	if (arr[nx][ny] == 2)arr[nx][ny] = 0;
	visit[nx][ny] = true;
	q.push({ nx,ny });
	}
	}
	}
	int main() {
	cin >> n >> m;
	int czcnt = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int x;
	cin >> x;
	if (x == 0)x = 2;
	else if (x == 1) {
	czcnt++;
	}
	arr[i][j] = x;
	}
	}
	bfs(0,0);// 1. 초기 외부 공기 설정
	int TIME = 0;
	while (czcnt>0) {
	// 2,3 반복
	TIME++;
	queue <xy> temp;
	// 2. 외부공기와 접촉해 있는 치즈 외부공기로 바꿔주기
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (arr[i][j] == 1) {
	int cnt = 0;
	for (int d = 0; d < 4; d++) {
	if (arr[i + dir[d][0]][j + dir[d][1]] == 0)cnt++;
	}
	if (cnt >= 2) {
	czcnt--;
	temp.push({ i,j }); // 새롭게 외부공기가 된 공기들 저장
	}
	}
	}
	}
	// 3. 내부공기였는데 외부공기와 접촉해 있다면 외부공기로 바꿔준다
	while (!temp.empty()) {
	int fx = temp.front().x;
	int fy = temp.front().y;
	temp.pop();
	arr[fx][fy] = 0;
	if (visit[fx][fy] == 0) {
	bfs(fx, fy);
	}
	}
	}
	cout << TIME << endl;
	//for (int i = 0; i < n; i++) {
	// for (int j = 0; j < m; j++) {
	// cout << arr[i][j] << " ";
	// }cout << endl;
	//}cout << endl;
	}

view raw [BOJ]2638.cpp hosted with ❤ by GitHub