문제

문제 링크

해설

• 시뮬레이션(구현) 문제 + DFS/BFS 문제이므로 문제에서 요구하는대로 시키는대로 그대로 구현하면 됩니다.
• 치즈가 남아있는 동안 while() 루프를 돌면서
  1. 시간(answer_time)을 증가하고
  2. 공기에 닿은 치즈 겉표면을 (아직 제거하진 않고) 표시만 하는 melt_cheese_before()를 호출합니다.
     • (0, 0)부터 DFS를 돌면서 치즈를 겉표면을 만나면 ‘2’로 표시한 뒤 return 합니다.
     • 이미 겉표면이면 그냥 return 합니다. (Edge case!)
     • 방문한 곳은 다시 방문하지 않습니다. (무한루프 방지!)
  3. 다음 루프에 치즈가 전부 사라지게 될 경우, 조각 개수(answer_pieces)를 카운트합니다.
  4. 다음 루프에 치즈가 남아있는 경우, 표시한 치즈 겉표면을 제거하는 melt_cheese_after()를 호출합니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, M;
int plate[100][100];
bool visited[100][100];

bool is_cheese_alive() {
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (plate[y][x] == 1) return true;
	return false;
}

void melt_cheese_before(int y, int x) {
	if (plate[y][x] == 2) return;
	if (plate[y][x] == 1) { plate[y][x] = 2; return; }

	visited[y][x] = true;
	for (auto i : d) {
		int ny = y + i[0], nx = x + i[1];
		if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx])
			melt_cheese_before(ny, nx);
	}
}

void melt_cheese_after() {
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (plate[y][x] == 2) plate[y][x] = 0;
}

void dfs(int y, int x) {
	visited[y][x] = true;
	for (auto i : d) {
		int ny = y + i[0], nx = x + i[1];
		if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[y][x]) dfs(ny, nx);
	}
}

int count_pieces() {
	int ret = 0;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (plate[y][x] == 2) dfs(y, x), ret++;
	return ret;
}

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 >> plate[y][x];

	int answer_time = 0, answer_pieces = 1;
	while (is_cheese_alive()) {
		answer_time++;

		melt_cheese_before(0, 0);
		memset(visited, false, sizeof(visited));

		if (!is_cheese_alive()) answer_pieces = count_pieces();

		melt_cheese_after();
	}
	cout << answer_time << '\n' << answer_pieces << '\n';
	return 0;
}

소스코드 링크

결과