BOJ 2636 치즈

사용한 알고리즘

알고리즘 설명

초기에 있던 모든 치즈의 크기를 알아낸다.
DFS를 이용하여 치즈를 녹이고 녹여진 치즈를 전체 치즈에서 줄이고 시간을 1시간씩 늘린다.
판 가장자리는 없으며 안쪽에 공기에 대해서는 신경쓰지 않아도 되므로 판 가장자리 한점(코드에서는 0,0)에서 부터 DFS를 시작하고, 공기에 닿아있는 모든 치즈를 녹인다.
계속 치즈를 녹이다가 치즈가 남지 않으면 그 시간을 출력한다.

풀이

// baekjoon 2636 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N=101;
const int dir[4][2] = {{0,-1}, {0,1}, {1,0}, {-1,0}};
int R, C, num;
int board[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

// (x, y) 좌표 치즈를 녹이기
int dfs(int x, int y) {
// 좌표 밖인 경우
	if (x < 0 || x >= R || y < 0 || y >= C) return 0;
// 이미 확인한 곳인 경우
	if (visited[x][y]) return 0;
// (x,y) 확인 시작
	visited[x][y]=true;

// 치즈가 있는경우
	if (board[x][y]) {
// 녹이고 끝낸다.
		board[x][y]=false;
		return 1;
	}

// 치즈가 없는경우 치즈를 찾아 떠난다.
	int ret = 0;
// (x,y) 상하좌우로 DFS를 진행한다.
	for (int d=0; d<4; d++)
		ret += dfs(x+dir[d][0], y+dir[d][1]);
	return ret;
}

int main() {

	scanf("%d%d", &R, &C);
	for (int i=0; i<R; i++)
		for (int j=0; j<C; j++)
			scanf("%d", &board[i][j]), num += board[i][j];
	int tmp = 0;
	int t = 0;
// num는 보드에 있는 치즈의 총량이다.
	while (num) {
		memset(visited, 0, sizeof(visited));
// 시간을 증가시킴
		t++;
// (0,0) 부터 녹이기 시작함 -> 판 가장자리는 항상 없음
		tmp = dfs(0,0);
		num -= tmp;
	}
	printf("%d\n%d\n", t, tmp);
	return 0;
}