백준 2636번: 치즈

[문제 링크]

2636번: 치즈

---

문제에서 치즈가 놓인 판을 객체로 표현하기 위해 클래스의 속성과 메서드를 다음과 같이 정의하였다.

Plate

- int 가로 길이 - int 세로 길이 - int 치즈조각 개수 - int[][] 치즈가 놓여있는 상태

+ void 초기의 치즈 상태를 세팅한다. + void 1시간마다 치즈를 녹인다. + int 남아있는 치즈조각의 개수를 반환한다.

 

알고리즘은 다음과 같다.

1. 치즈를 놓을 판의 객체를 생성한다.

2. 가로 길이와 세로 길이를 입력 받은 다음, 치즈가 놓여있는 상태를 입력받아 배열에 담는다.

3. 판 위에 놓인 치즈가 모두 녹을 때 까지 (0, 0)을 시작점으로 하는 BFS를 수행하여 치즈를 녹인다.

4. 치즈가 모두 녹았다면 경과한 시간과 1시간 전에 남아있던 치즈의 개수를 출력한다.

---

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

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

struct Pos {
	int y;
	int x;
};

class Plate {
private:
	int col, row;
	int cheezeCnt;
	int arr[101][101];
public:
	Plate() : cheezeCnt(0), col(0), row(0) {
		memset(arr, sizeof(arr), 0);
	}

	void setPlate() {
		cin >> col >> row;

		for (int i = 0; i < col; i++)
			for (int j = 0; j < row; j++) {
				cin >> arr[i][j];

				if (arr[i][j] == 1) cheezeCnt++;
			}
	}

	// bfs
	void meltCheeze() {
		bool visited[101][101] = { false };
		int tempArr[101][101];
		memcpy(tempArr, arr, sizeof(tempArr));

		queue<Pos> q;
		q.push({ 0,0 });
		visited[0][0] = true;

		while (!q.empty()) {
			Pos here = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				Pos there = { here.y + dy[i], here.x + dx[i] };
				if (there.y < 0 || there.y >= col || there.x < 0 || there.x >= row)
					continue;

				if (tempArr[there.y][there.x] == 0 && !visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					q.push(there);
				}
				else if (tempArr[there.y][there.x] == 1 && !visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					arr[there.y][there.x] = 0;
					cheezeCnt--;
				}
			}
		}
	}

	int getCheezeCount() {
		return cheezeCnt;
	}
};

void printAllMeltTime(Plate& plate) {
	int time = 0;
	int lastCheezeCnt = plate.getCheezeCount();

	while (1) {
		plate.meltCheeze();
		time++;

		if (plate.getCheezeCount() != 0)
			lastCheezeCnt = plate.getCheezeCount();
		else
			break;
	}

	cout << time << '\n' << lastCheezeCnt << endl;
}

int main(void) {
	Plate plate;
	plate.setPlate();
	printAllMeltTime(plate);

	return 0;
}