언제나 처음처럼

[문제 링크]

간단해보이지만 함정이 하나 있는 문제였다.

치즈가 공기와 접촉하는지 확인하기 위해 치즈 기준 동서남북 방향에 0이 있는지 체크하고 0이 두군데 이상 있다면 공기와 접촉하고 있다고 단정 지을 수 있는데, 치즈로 둘러 쌓인 내부의 0은 공기가 통하지 않기 때문에 이를 제외시켜줘야 한다.

따라서, 치즈를 녹이기 전에 {0, 0} 좌표를 시작으로 BFS를 수행하여 실제로 공기가 통하는 좌표를 먼저 마킹했다.

그 다음 전체 판을 탐색하여 공기와 접해있는 면이 2개 이상인 치즈를 녹이는 방식으로 구현하였다.

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

int N, M, cheezeCnt = 0;
int board[101][101];
bool isAir[101][101];

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

void markingAir() {
	queue<pair<int, int>> q;
	memset(isAir, false, sizeof(isAir));

	q.push({ 0,0 });
	isAir[0][0] = true;

	while (!q.empty()) {
		int hereY = q.front().first;
		int hereX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nearY = hereY + dy[i];
			int nearX = hereX + dx[i];
			if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < M) {
				if (board[nearY][nearX] == 0 && !isAir[nearY][nearX]) {
					q.push({ nearY, nearX });
					isAir[nearY][nearX] = true;
				}
			}
		}
	}
}

void meltCheeze() {
	int temp[101][101];

	memcpy(temp, board, sizeof(board));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 1) {
				int air = 0;

				for (int k = 0; k < 4; k++) {
					int nearY = i + dy[k];
					int nearX = j + dx[k];
					if (isAir[nearY][nearX])
						air++;
				}

				if (air >= 2) {
					board[i][j] = 0;
					cheezeCnt--;
				}
			}
		}
	}
}

int getAllMeltCheezeTime() {
	int time = 0;

	while (cheezeCnt) {
		markingAir();
		meltCheeze();
		time++;
	}

	return time;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			int n;
			cin >> n;
			board[i][j] = n;
			if (board[i][j] == 1)
				cheezeCnt++;
		}

	cout << getAllMeltCheezeTime() << endl;

	return 0;
}

[문제 링크]

이진트리의 전위순회, 중위순회, 후위순회를 구현하는 문제였다.

이진트리에서 노드는 자식노드를 가지고 있지 않더라도 공집합 노드를 가지고있는 하나의 이진트리라고 볼 수 있기 때문에 별도의 노드 구조체를 정의하지 않고, BTree 클래스를 정의하여 구현하였다.

#include <iostream>
using namespace std;

class BTree {
	char data;
	BTree* left;
	BTree* right;
public:
	BTree(char c) : data(c), left(NULL), right(NULL) { }
	
	void makeLeftSubTree(BTree* sub) {
		this->left = sub;
	}

	void makeRightSubTree(BTree* sub) {
		this->right = sub;
	}

	void printData() {
		cout << data;
	}

	BTree* findNode(char c) {
		BTree* node = NULL;

		if (this->data == c)
			node = this;
		if (left != NULL && node == NULL) node = left->findNode(c);
		if (right != NULL && node == NULL) node = right->findNode(c);

		return node;
	}

	void preorder() {
		printData();
		if(left != NULL)  left->preorder();
		if(right != NULL) right->preorder();
	}

	void inorder() {
		if (left != NULL)  left->inorder();
		printData();
		if (right != NULL) right->inorder();
	}

	void postorder() {
		if (left != NULL)  left->postorder();
		if (right != NULL) right->postorder();
		printData();
	}

	void deleteTree() {
		if (left != NULL)
			left->deleteTree();
		if (right != NULL)
			right->deleteTree();

		delete this;
	}
};

int main(void) {
	int N;
	cin >> N;

	BTree* tree = new BTree('A');
	for (int i = 0; i < N; i++) {
		char parent, left, right;
		cin >> parent >> left >> right;

		if (left != '.') {
			BTree* lNode = new BTree(left);
			tree->findNode(parent)->makeLeftSubTree(lNode);
		}
		if (right != '.') {
			BTree* rNode = new BTree(right);
			tree->findNode(parent)->makeRightSubTree(rNode);
		}
	}

	tree->preorder();
	cout << '\n';
	tree->inorder();
	cout << '\n';
	tree->postorder();

	tree->deleteTree();

	return 0;
}

[문제 링크]

왠지 영어로 된 알고리즘 문제를 풀어봐야 할 것 같아서 풀게되었다.

문제는 간단했다. 한 블록을 뒤집으면 상하좌우에 존재하는 블록들까지 동시에 뒤집어지는데, 모든 블록을 블랙 또는 화이트가 되도록 만들기 위해 뒤집는 최소한의 횟수를 구하는 문제였다.

최소한의 횟수를 구하기 위해 bfs를 구현하면 간단히 풀 수 있는 문제인데, 한가지 문제가 있다면 이전에 등장했던 보드판의 상태를 중복탐색 하는 것을 막기 위해 방문체크를 해줘야 하는데, 블록의 형태를 어떻게 표현할 것인지가 문제였다.

보드판은 항상 4x4 이므로 보드판에 존재하는 블록의 개수 또한 항상 16개라는 것을 알 수 있다.

따라서, 비트마스크 기법을 활용하면 보드판의 상태를 integer 타입의 정수형 데이터로 표현하는 것이 가능하다.

보드판의 좌표 (y,x)를 (4*y)+x 공식에 대입하여 자릿수를 구한 다음, OR 연산을 통해 해당 자릿수의 값을 블랙일 경우 1, 화이트일 경우 0으로 세팅하고, 공을 뒤집는 작업은 XOR 연산을 통해 값을 반전시켜줌으로써 간단하게 보드판을 관리할 수 있다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

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

int ptod(int y, int x) {
	return (y * 4) + x;
}

int bfs(int start) {
	int allBlack = (1 << 16) - 1;
	int allWhite = 0;
	bool visited[(1 << 16)] = { false };

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

	while (!q.empty()) {
		int here = q.front().first;
		int round = q.front().second;
		q.pop();

		if (here == allBlack || here == allWhite)
			return round;

		for(int i=0; i<4; i++)
			for (int j = 0; j < 4; j++) {
				int there = here;
				there ^= (1 << (ptod(i, j)));

				for (int k = 0; k < 4; k++) {
					int nextY = i + dy[k];
					int nextX = j + dx[k];
					if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
						there ^= (1 << (ptod(nextY, nextX)));
					}
				}
				if (!visited[there]) {
					visited[there] = true;
					q.push({ there, round + 1 });
				}
			}
	}

	return -1;
}

int solution(vector<string>& input) {
	int inputNumber = 0;
	for(int i=0; i<4; i++)
		for (int j = 0; j < 4; j++) {
			int digit = ptod(i, j);
			if (input[i][j] == 'b')
				inputNumber |= (1 << digit);
		}

	return bfs(inputNumber);
}

int main(void) {
	vector<string> input;
	for (int i = 0; i < 4; i++) {
		string s;
		cin >> s;
		input.push_back(s);
	}

	int result = solution(input);
	if (result != -1)
		cout << result;
	else
		cout << "Impossible";

	return 0;
}

[문제 링크]

어떤 문제를 풀기 위해서 먼저 풀어야 하는 문제가 있다고 한다. 이때 어떤 문제는 먼저 풀어야 하는 문제에 의존적이라고 할 수 있다.

이 문제처럼 정점끼리 서로 의존성이 존재하는 경우 위상정렬을 통해 올바른 순서를 찾을 수 있다.

이전까지는 DFS를 수행한 결과를 역순으로 출력하여 위상정렬을 수행하는 방법만 알고 있었는데,

이 문제를 통해 들어오는 간선의 개수(in degree)를 이용하여 위상정렬을 수행하는 방법을 새롭게 알게 되었다.

ps// 아래 블로그를 참고하여 풀었는데, 위상정렬에 대한 설명이 잘 되어있는 것 같다.

jason9319.tistory.com/93

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

vector<int> adj[32001];
int indegree[32001];

vector<int> topologicalSort(int N) {
	priority_queue<int> pq;
	for (int i = 1; i <= N; i++)
		if (indegree[i] == 0)
			pq.push(-i);
	
	vector<int> order;
	while (!pq.empty()) {
		int here = -pq.top();
		pq.pop();

		order.push_back(here);
		
		for (auto x : adj[here]) {
			indegree[x]--;
			if (indegree[x] == 0)
				pq.push(-x);
		}
	}
	return order;
}

int main(void) {
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		adj[A].push_back(B);
		indegree[B]++;
	}

	vector<int> result = topologicalSort(N);

	for (auto x : result)
		cout << x << ' ';

	return 0;
}

[문제 링크]

백트래킹과 BFS를 활용하여 풀 수 있는 문제였다.

입력으로 주어지는 바이러스들과 그 바이러스를 M개 활성화 시키는 모든 경우의 수를 백트레킹을 통해 완전탐색 하고, 모든 경우에 대해 바이러스를 확산시키는 BFS를 수행하여 가장 빠르게 확산되는 시간을 구해주면 원하는 결과를 얻을 수 있다.

시간이 0.25초로 제한되어 있기 때문에 2차원배열 전체를 순회하며 활성화 된 바이러스가 있는 위치를 찾아 확산시키는 방식으로 BFS를 구현하게 된다면 최악의 경우  (50^2) * (10개중 5개를 뽑는 조합의 수 252) * 50 =  31,500,000번 연산을 수행해야 하므로 제한 시간을 초과하게 된다. 따라서 배열 전체를 순회하는 방식이 아닌, 활성화 된 바이러스의 위치를 따로 저장하여 바이러스가 존재하는 좌표에 바로 접근할 수 있도록 구현하였다.

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

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N, M, cnt = 0, blank = 0;
int leastTime = INF;
int board[50][50];
Pos virus[10];

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

int bfs(list<Pos> actVirus) {
	bool visited[50][50] = { false };
	for (auto x : actVirus)
		visited[x.y][x.x] = true;

	int change = 0;

	queue <int> q;
	q.push(0);

	while (!q.empty()) {
		int time = q.front();
		q.pop();

		if (change == blank) return time;
//		bool isChange = false;

		int listSize = actVirus.size();
		for (int i = 0; i < listSize; i++) {
			Pos here = actVirus.front();
			actVirus.pop_front();

			for (int j = 0; j < 4; j++) {
				int nearY = here.y + dy[j];
				int nearX = here.x + dx[j];
				if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < N && !visited[nearY][nearX])
					if (board[nearY][nearX] == 2 || board[nearY][nearX] == 0) {
						visited[nearY][nearX] = true;
//						isChange = true;
						actVirus.push_back({ nearY, nearX });
						if (board[nearY][nearX] == 0)
							change++;
					}
			}
		}
//		if (isChange) q.push(time + 1);
		if (!actVirus.empty()) q.push(time + 1);
	}

	return INF;
}

void backtracking(int start, list<Pos>& actVirus) {
	int select = actVirus.size();
	if (select == M) {
		leastTime = min(leastTime, bfs(actVirus));
		return;
	}

	for (int i = start; i < cnt; i++) {
		Pos pos = virus[i];
		actVirus.push_back({ pos.y, pos.x });
		backtracking(i + 1, actVirus);
		actVirus.pop_back();
	}
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				virus[cnt].y = i;
				virus[cnt].x = j;
				cnt++;
			}
			else if (board[i][j] == 0)
				blank++;
		}

	list<Pos> actVirus;
	backtracking(0, actVirus);

	if (leastTime == INF)
		cout << -1 << endl;
	else
		cout << leastTime << endl;

	return 0;
}

[문제 링크]

문제를 풀기에 앞서 땅을 표현하는 Land 클래스와 로봇을 표현하는 Robot 클래스를 설계하였다.

로봇은 땅에 양분을 공급하는 역할을 수행한다. 따라서 Robot 클래스의 supplyNutrients() 메서드에서 Land 객체의 레퍼런스 타입을 매개변수로 받아 Land 클래스의 increaseNutrients() 메서드를 호출하여 땅에 양분을 공급하도록 설계하였다. 

Robot 클래스의 메서드에서 Land 클래스를 매개변수로 받는 형태를 이루고 있기 때문에 이 둘은 서로 연관 관계임을 알 수 있다. 따라서 연관 관계를 뜻하는 점선 화살표로 두 클래스를 연결하였다.

알고리즘은 다음과 같다.

1. N, M, K를 입력 받는다. 그다음 Land Size 값을 N으로 초기화한 Land 객체와 Robot 객체를 생성한다.

2. H2D2가 땅에 공급하는 양분을 배열로 입력 받아 설정한다.

3. 문제에서 요구하는 대로 봄, 여름, 가을, 겨울에 나타나는 일들을 그대로 구현한다.

4. 봄->여름->가을->겨울 순으로 함수를 호출한다. 그리고 이를 K번 반복한다.

5. K번 반복한 후 땅에 심어진 나무의 개수를 출력한다.

// 봄에 나무가 양분을 흡수하는 과정에서 나이가 어린 나무부터 양분을 먹도록 구현하기 위해 우선순위큐를 사용할 경우 나무를 심을 때마다 매번 정렬을 수행하게 되므로 시간복잡도가 커지게 된다.

따라서 나무를 vector에 담은 다음 나무가 양분을 흡수하는 작업이 실행되기 전에 정렬이 이루어지도록 구현하는 것이 효율적이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Land {
private:
	int landSize;
	int nutrients[11][11];
	vector<int> livingTree[11][11];
	queue<int> deadTree[11][11];
public:
	Land(int N) : landSize(N) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				nutrients[y][x] = 5;
			}
		}
	}

	// 현재 심어진 나무의 개수를 반환한다.
	int getTreeCount() {
		int treeCnt = 0;
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				treeCnt += livingTree[y][x].size();
			}
		}

		return treeCnt;
	}

	// 나무를 심는다
	void plantTree(int y, int x, int treeAge) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize) {
			livingTree[y][x].push_back(treeAge);
		}
		else
			return;
	}

	// 나무가 땅의 양분을 흡수한다.
	void nourishTheTree() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				queue<int> growingTree;

				sort(livingTree[y][x].begin(), livingTree[y][x].end(), greater<int>());

				while (!livingTree[y][x].empty()) {
					int treeAge = livingTree[y][x].back();
					livingTree[y][x].pop_back();

					if (nutrients[y][x] >= treeAge) {
						nutrients[y][x] -= treeAge;
						growingTree.push(treeAge + 1);
					}
					else {
						deadTree[y][x].push(treeAge);
					}
				}

				while (!growingTree.empty()) {
					int treeAge = growingTree.front();
					growingTree.pop();

					livingTree[y][x].push_back(treeAge);
				}
			}
		}
	}

	// 땅의 양분을 증가시킨다.
	void increaseNutrients(int y, int x, int val) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize)
			nutrients[y][x] += val;
		else
			return;
	}

	// 죽은 나무가 땅의 양분으로 변환된다.
	void convertToNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				while (!deadTree[y][x].empty()) {
					int newNutrients = deadTree[y][x].front() / 2;
					deadTree[y][x].pop();

					increaseNutrients(y, x, newNutrients);
				}
			}
		}
	}

	// 나이가 5의 배수인 나무가 번식한다.
	void treeMultiply() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				int treeSize = livingTree[y][x].size();
				for (int i = 0; i < treeSize; i++) {
					int treeAge = livingTree[y][x][i];
					if (treeAge % 5 == 0) {
						for (int i = -1; i < 2; i++) {
							for (int j = -1; j < 2; j++) {
								if (i == 0 && j == 0) continue;
								plantTree(y + i, x + j, 1);
							}
						}
					}
				}
			}
		}
	}
};

class Robot {
private:
	int landSize;
	int nutrients[11][11];
public:
	Robot(int N) : landSize(N) { }

	// 공급하는 양분의 양을 설정한다.
	void setNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				cin >> nutrients[y][x];
			}
		}
	}

	// 땅에 양분을 공급한다.
	void supplyNutrients(Land& land) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				land.increaseNutrients(y, x, nutrients[y][x]);
			}
		}
	}
};

void springAction(Land& land) {
	land.nourishTheTree();
}

void summerAction(Land& land) {
	land.convertToNutrients();
}

void fallAction(Land& land) {
	land.treeMultiply();
}

void winterAction(Land& land, Robot& robot) {
	robot.supplyNutrients(land);
}

void printYearsHavePassed(Land& land, Robot& robot, int K) {
	for (int i = 0; i < K; i++) {
		springAction(land);
		summerAction(land);
		fallAction(land);
		winterAction(land, robot);
	}

	cout << land.getTreeCount() << endl;
}

int main(void) {
	int N, M, K;
	cin >> N >> M >> K;

	Land land(N);
	Robot S2D2(N);

	S2D2.setNutrients();

	for (int i = 0; i < M; i++) {
		int x, y, z;
		cin >> y >> x >> z;
		land.plantTree(y, x, z);
	}

	printYearsHavePassed(land, S2D2, K);

	return 0;
}

[문제 링크]

문제를 풀기에 앞서 문제에서 주어진 지도와 경사로, 그리고 지도와 경사로를 이용해 지나갈 수 있는 길인지 파악하는 역할을 하는 사람을 클래스 다이어그램으로 표현하였다.

사람은 지형이 그려진 지도와 설치할 수 있는 경사로를 "가지고" 있다고 볼 수 있기 때문에

"사람은 지도와 경사로를 포함한다." 라는 has-A 관계가 성립된다.

따라서 필자는 클래스 다이어그램을 다음과 같이 작성하였다.

알고리즘은 다음과 같다.

1. 입력받은 정보를 통해 지도와 경사로 객체를 생성한다.

2. 지도와 경사로 객체를 속성으로 가지는 사람 객체를 생성한다.

3. 한쪽 끝에서 반대쪽 끝으로 가는 길을 찾는 것이기 때문에 1열의 모든 좌표에서 아래방향으로 탐색하고, 1행의 모든 좌표에서 오른쪽 방향으로 탐색하여 가능한 길의 갯수를 샌다.

 3-1. IF 현재 지형의 높이가 이전 지형의 높이와 같다면 경사로를 놓을 필요 없이 다음 지형으로 넘어간다.

ELSE IF 현재 지형의 높이가 더 낮다면 현재 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

ELSE IF 현재 지형의 높이가 더 높다면 경사로의 길이 L만큼 뒤에 위치한 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

추가로, 이미 경사로를 설치한 지형에 중복으로 설치할 수 없으므로 경사로 설치 여부를 저장하는 배열을 통해 중복 설치를 방지하였다.

#include <iostream>
using namespace std;

class Map {
private:
	int N;
	int arr[101][101];

public:
	Map() : N(0) {}
	Map(int _N) : N(_N) {}

	void setTopography() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> arr[i][j];
	}

	int getMapSize() {
		return N;
	}

	int getTopographyHeight(int y, int x) {
		if (y < 0 || y >= N || x < 0 || x >= N)
			return 0;

		return arr[y][x];
	}
};

class Runway {
private:
	int L;

public:
	Runway() : L(0) {}
	Runway(int _L) : L(_L) {}

	int getRunwayLength() {
		return L;
	}
};

enum {
	RIGHT, DOWN
};

class Person {
private:
	Map map;
	Runway runway;

	int readMap(int y, int x) {
		return map.getTopographyHeight(y, x);
	}

	bool isLayRunway(int y, int x, int height, bool layRunway[][101], int state) {
		int L = runway.getRunwayLength();

		switch (state) {
		case RIGHT:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y, x + i);
				if (layRunway[y][x + i] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y][x + i] = true;
			}
			return true;

		case DOWN:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y + i, x);
				if (layRunway[y + i][x] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y + i][x] = true;
			}
			return true;
		}

		return false;
	}
public:
	Person(Map& _map, Runway& _runway) {
		this->map = _map;
		this->runway = _runway;
	}

	bool isCheckPath(int y, int x, int state) {
		int N = map.getMapSize();
		int L = runway.getRunwayLength();

		if (y >= N || x >= N) return false;

		bool layRunway[101][101] = { false };
		int lastHeight = readMap(y, x);

		switch (state) {
		case RIGHT:
			while (++x < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, RIGHT))
						return false;
					x += L - 1;
				}
				else {
					x -= L;
					if (!isLayRunway(y, x, height, layRunway, RIGHT))
						return false;
					x += L;
				}

				lastHeight = height;
			}
			return true;

		case DOWN:
			while (++y < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, DOWN))
						return false;
					y += L - 1;
				}
				else {
					y -= L;
					if (!isLayRunway(y, x, height, layRunway, DOWN))
						return false;
					y += L;
				}

				lastHeight = height;
			}
			return true;
		}

		return false;
	}
};

void printAllPath(Map& map, Runway& runway) {
	Person person(map, runway);
	int pathCnt = 0;

	for (int y = 0; y < 100; y++)
		if (person.isCheckPath(y, 0, RIGHT)) {
			pathCnt++;
		}

	for (int x = 0; x < 100; x++)
		if (person.isCheckPath(0, x, DOWN)) {
			pathCnt++;
		}

	cout << pathCnt << endl;
}

int main(void) {
	int N, L;
	cin >> N >> L;

	Map map(N);
	Runway runway(L);

	map.setTopography();
	printAllPath(map, runway);

	return 0;
}

[문제 링크]

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

알고리즘은 다음과 같다.

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;
}