[구름 알고리즘 먼데이 챌린지] Week4 : 2. 단풍나무

문제

가을이 되면서, 단풍나무가 물들기 시작하려고 한다. 구름공원에서는 크기가 N*N인 땅에 단풍나무를 많이 심어두었다.

구름공원은 땅을 효율적으로 관리하기 위해, 땅을 1*1 크기의 작은 구역 단위로 나눈 뒤 해당 구역에 심어진 나무들을 묶어서 관리하고 있다. N=4일 때 공원은 아래와 같이 16개의 작은 구역으로 나눠지게 되고, 각 구역의 이름은 아래와 같다.

 

구름공원의 관리자 구름이는 모든 단풍나무가 물드는 시점을 파악하려고 한다. 단풍나무가 물드는 규칙은 아래와 같다.

●arr[i][j]에는 해당 구역에 아직 물들지 않은 단풍나무의 수가 적혀 있다.

●arr[i][j]의 값이의 값이 0이면, 해당 구역의 모든 단풍나무가 물들었다는 것을 의미한다.

●arr[i][j]의 값은 매일 밤마다 상하좌우로 인접한 구역 중 그날 아침 기준으로 단풍나무가 모두 물들어 있는 구역의 수만큼 줄어든다. 만약 그러한 구역의 수가 arr[i][j]보다 크다면, arr[i][j]의 값은 0이 된다.

구름공원에는 모든 단풍나무가 물들어 있는 구역이 최소 한 곳 이상은 존재한다고 할 때, 구름이를 도와 며칠 후에 모든 단풍나무가 물들지 출력하시오.

 

크게 두 가지  Action을 정의했다.

1.check() : 구름 공원의 모든 단풍나무가 물들었는지 확인

2.simulation() : 0이 아닌 모든 좌표에서 물들지 않은 단풍나무 감소시키기 

 

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

int n;
vector<vector<int>> board(41, vector<int>(41));
vector<vector<int>> temp(41, vector<int>(41));
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] != 0) return true;
		}
	}
	return false;
}

void simulation(int cy, int cx) {
	int cnt = 0, ny, nx;
	for (int i = 0; i < 4; i++) {
		ny = cy + dy[i]; nx = cx + dx[i];
		if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1) continue;
		if (board[ny][nx] == 0) cnt++;
	}
	temp[cy][cx] = temp[cy][cx] < cnt ? 0 : temp[cy][cx] - cnt;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> board[i][j];

	int day = 0;
	while (check()) {
		day++;
		temp = board;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (board[i][j] != 0) simulation(i, j);
        //모든 simulation 작업을 수행 한 뒤 변경 사항을 한 번에 board에 적용
		board = temp;
	}
	cout << day;
	return 0;
}

앞서 (i, j)에서 simulation을 진행한 결과가 (i, j+1)에서의 simulation에 영향을 미치지 않아야 하므로 temp 2차원 배열을 생성하였다.

즉, 하루에 (i,j)에서 진행되는 모든 simulation은 board를 기준으로 주변(상하좌우)을 확인(0인 좌표의 수)하고 board가 아닌 temp[i][j]에 값을 변경 시키는 것이다. 이 후, 모든 simulation 작업을 수행 한 뒤 변경 사항을 한 번에 board에 적용시켜 주는 것이다.