급하게임개발

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

이 문제의 경우 dfs로 풀이를 진행했다  이 문제를 풀 때 한가지 잘못 생각한점으 치즈 안의 공간은 실내온도에 접촉 한것이아니라는 것이었다.  문제에서 테두리에는 치즈가 없다고 명시해주었으므로 dfs혹은 bfs로 0,0 위치 와 연결된 공간들을 모두 -1  로 체크 해주었다 그후 dfs를 한번더 진행하여 치즈들중 외부공기 2층이랑 이어진 공간들에 대해서 다른 배열에 넣어서 계산해주고 다시 0,0부터 dfs를 돌려 외부공기를 체크해 주었다.

#include <iostream>
using namespace std;
int N, M;
int arr[100][100];
int willMelt[100][100];
int xIdx[4] = { 1,0,-1,0 };
int yIdx[4] = { 0,1,0,-1 };
bool isVisited[100][100] = { 0, };
bool canGo(int x, int y) {
	if (x < N && y < M && x >= 0 && y >= 0) {
		if (!isVisited[x][y] && (arr[x][y] == 1))
			return true;
		else
			return false;
	}
	else
		return false;
}
void copyArr(int arr[100][100], int arr2[100][100]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			arr[i][j] = arr2[i][j];
		}
}
void dfs(int x, int y) {
	int zeroCount = 0;
	for (int i = 0; i < 4; i++) {
		if (arr[x + xIdx[i]][y + yIdx[i]] == -1) {
			zeroCount += 1;
		}
		if (canGo(x + xIdx[i], y + yIdx[i])) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			dfs(x + xIdx[i], y + yIdx[i]);
		}
	}
	if (zeroCount >= 2) {
		willMelt[x][y] = 0;
	}

}
void airDfs(int x, int y) {
	arr[x][y] = -1;
	for (int i = 0; i < 4; i++) {
		if (x + xIdx[i] < N && y + yIdx[i] < M && x + xIdx[i] >= 0 && y + yIdx[i] >= 0 && !isVisited[x + xIdx[i]][y + yIdx[i]]&& (arr[x + xIdx[i]][y + yIdx[i]] == 0|| arr[x + xIdx[i]][y + yIdx[i]] == -1)) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			arr[x + xIdx[i]][y + yIdx[i]] = -1;
			airDfs(x + xIdx[i], y + yIdx[i]);
		}
	}


}
void meltCheese() {
	copyArr(willMelt, arr);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!canGo(i, j))
				continue;
			isVisited[i][j] = true;
			dfs(i, j);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	copyArr(arr, willMelt);
}
bool isMelted() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] != -1)
				sum += 1;
		}
	}
	if (sum == 0)
		return true;
	else
		return false;
}
void process() {
	int year = 0;
	airDfs(0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	while (!isMelted()) {
		meltCheese();
		airDfs(0, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				isVisited[i][j] = false;
			}
		}
		year += 1;
	}
	cout << year;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}
	process();
}