[c++] 백준 2636, 치즈

백주 2636

🌲 문제 요약

사각형 모양의 판과 한 조각의 치즈가 주어졌을 때, 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전, 치즈가 남아 있는 칸의 개수를 구하는 문제.

🌲 문제 풀이

while문 내부에서 dfs 함수를 이용해 치즈의 테두리 부분을 반복하여 탐색한다. dfs 함수는 배열 a를 탐색하여 만약 a[y][x]의 값이 1이라면, 벡터 v에 해당 좌표를 저장한다.
a의 모든 값이 0이 될 때까지 반복하며, cnt1에는 치즈가 녹는 데 걸린 시간, cnt2에는 치즈가 남아 있는 칸의 개수를 저장한다.

🌲 주의

한 번의 반복이 끝날 때마다, visited 배열의 값을 0으로 초기화한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, a[105][105], visited[105][105];
vector<pair<int, int>> v;

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

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int cnt1 = 0, cnt2;
	while (1) {
		memset(visited, 0, sizeof(visited));
		v.clear();
		cnt2 = 0;
		dfs(0, 0);
		for (pair<int, int> b : v) {
			a[b.first][b.second] = 0;
			cnt2++;
		}
		bool flag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (a[i][j] == 1) {
					flag = 1;
					break;
				}
			}
		}
		cnt1++;
		if (!flag) break;
	}
	cout << cnt1 << '\n' << cnt2 << '\n';
	
	return 0;
}