[백준] 2638번 치즈 C++ 코드

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int dx[] = { 0,0,1,-1 };
const int dy[] = { 1,-1,0,0 };

int n, m, a[103][103], visited[103][103], res;
vector<pair<int, int>> v;
vector <pair<int, int>> me;

// 치즈 탐색
void dfs(int x, int y) {
	visited[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= n || ny >= m || nx < 0 || ny < 0 || visited[nx][ny]) continue;
		if (a[nx][ny] == 0) dfs(nx, ny);
		else {
			visited[nx][ny] = 1;
			v.push_back(make_pair(nx, ny));
		}
	}
}

// 치즈 구멍 포함되는 것을 막아야 한다
void isMelting() {
	for (pair<int, int > pa : v) {
		int x = pa.first;
		int y = pa.second;
		int tmp = 0;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= n || ny >= m || nx < 0 || ny < 0) continue;
			if (a[nx][ny] == 0 && visited[nx][ny]) tmp++;
		}
		if (tmp >= 2) me.push_back(make_pair(x, y));
	}
}

// 녹이기
void melting() {
	isMelting();
	for (pair<int, int > pa : me) {
		a[pa.first][pa.second] = 0;
	}
	v.clear();
	me.clear();
	fill(&visited[0][0], &visited[0][0] + 103 * 103, 0);
}

// 치즈가 있는지 없는지 확인
bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j]) return false;
		}
	}
	return true;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	while (1) {
		if (check()) break;
		dfs(0, 0);
		melting();
		res++;
	}

	cout << res << '\n';
	return 0;
}

풀이

가장자리에는 치즈가 존재하지 않는다고 했으므로 (0,0)에서 탐색을 시작했다. 바깥쪽에 있는 치즈를 우선 찾아준다. 그 후 2개와 접해있는지 확인한다. 이때 주의해야할 점은 구멍과 구분해주어야 한다. 이미 방문처리 된 부분인 동시에 0인 부분은 바깥쪽에 있다는 뜻이므로 녹여주면 된다. 모두 녹았다면 걸린 시간을 출력해주면 된다.

 

치즈를 녹일 때 한 번에 동시에 녹이지 않으면 현재 상태가 영향을 줄 수 있으므로 주의해야 한다.