백준 2636번 - 치즈

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

2636번: 치즈

풀이 과정

 가장 외곽 그래프와 접촉하는 1(치즈)인 그래프가 차례로 녹을 때, 치즈가 다 없어질 때까지 걸리는 시간과 마지막에 남았던 치즈의 개수를 구하는 문제이다.

 

 지도에서 가장 바깥 쪽 4면은 비어 있으므로 바깥 중 한 곳에서 완전 탐색을 해주면 된다. 완전 탐색으로 접촉한 치즈면을 0으로 바꾸고 최종적으로 치즈가 없어질 때까지 진행한다. DFS를 사용했고 0인 부분을 탐색하며 ny, nx 값을 체크하며 치즈인지 확인하고 값과 visited를 갱신했다.

 

느낀 점

 문제가 가장자리 4면을 비워두어서 쉽게 풀 수 있었다. 만약 그게 아니라면 연결 컴포넌트를 구하고, 공기와 접촉하는지 확인하고, 함수를 실행 해야할 것이다.

 

#include<bits/stdc++.h>
using namespace std;

const int MAX = 100;
int n, m, cnt, t, ret, _prev;
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
int mp[MAX][MAX], visited[MAX][MAX];
bool flag;

//그래프를 모두 순회하며 주변 치즈를 녹임
void DFS_melting(int y, int x) {
	if (visited[y][x] || mp[y][x]) return;
	visited[y][x] = 1;
	for (int d = 0; d < 4; d++) {
		int ny = my[d] + y;
		int nx = mx[d] + x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if (mp[ny][nx] == 1) {
			visited[ny][nx] = 1;
			mp[ny][nx] = 0;
		}
		else {
			DFS_melting(ny, nx);
		}
	}
	return;
}

//치즈가 있는지 확인하고, 치즈 개수를 갱신
bool is_clear() {
	bool flg = false; cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mp[i][j] == 1) {
				flg = true; cnt++;
			}
		}
	}
	
	if (!flg) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
		}
	}

	//치즈가 없을 때까지 녹이기
	while (!is_clear()) {
		fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
		DFS_melting(0, 0);
		_prev = cnt; t++; //녹기 전 치즈 개수 저장
	}
	
	//출력
	cout << t << "\n" << _prev;

	return 0;
}