알고리즘 :: 백준 :: 2636 - 치즈

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 가로, 세로 ≤ 100
• 출력: 치즈가 모두 녹는데 걸리는 시간, 모두 녹기 직전에 남아있던 치즈 칸 개수

✏️ 문제풀이

시뮬레이션(구현) + DFS/BFS 문제로, 문제가 요구하는대로 그대로 구현하면 됩니다.

하지만, 바로 코딩에 들어가지 마시고 순서대로 어떤 절차를 밟을지 간단하게나마 손코딩을 한 후 진행합시다.

1. `while(치즈가 남아있는 동안)` - 전체 칸을 순회하며 치즈가 있는지 확인하는 함수가 필요합니다.
2. `(0, 0)` 공기를 시작점으로 DFS 또는 BFS를 돌려서 치즈를 만나면 '녹았다' 표시를 합니다.
   1. `(0, 0)`은 무조건 공기입니다. 문제에 '가장자리에는 치즈가 없다'고 나와있기 때문입니다.
   2. 이 과정이 끝나면, 공기와 맞닿은 치즈는 '녹았다' 표시가 완료됩니다.
3. 전체 칸을 순회하며 '녹았다' 표시가 된 치즈를 찾고, 빈칸으로 만듭니다.
   1. 이때, 치즈 개수도 함께 카운트 합니다.
   2. 여기서 카운트한 치즈 개수는 '녹기 전' 치즈 칸 수가 되겠습니다.

짧게 요약하면, (치즈가 있다면) → (치즈 '녹았다' 표시) → (치즈 카운트 + 표시된 치즈 녹이기)를 반복하면 되겠습니다.

📝 코드

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

constexpr int dy[] = {-1, 0, 1, 0};
constexpr int dx[] = {0, 1, 0, -1};
enum { EMPTY, CHEESE, MELTED };

int N, M;
array<array<int, 101>, 101> arr;
array<array<bool, 101>, 101> visited;

inline bool isThereCheese() {
	bool ret = false;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			if (arr[y][x] == CHEESE) ret = true;
	return ret;
}

inline int melt() {
	int ret = 0;
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			if (arr[y][x] != EMPTY) {
				ret++;	// count cheese before melt
				if (arr[y][x] == MELTED) arr[y][x] = EMPTY;
			}
		}
	}
	return ret;
}

void melting(int y, int x) {
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i], nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
		if (arr[ny][nx] == CHEESE) arr[ny][nx] = MELTED;
		else if (arr[ny][nx] == EMPTY) melting(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			cin >> arr[y][x];
	int ans_time = 0, ans_cnt = 0;
	while (isThereCheese()) {
		ans_time++;
		melting(0, 0);
		ans_cnt = melt();
		memset(&visited[0][0], false, sizeof(visited));
	}
	cout << ans_time << '\n';
	cout << ans_cnt << '\n';
}

 

🔗 코드 링크

🕧 결과