[코드트리] 나무박멸 (C++)

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[설명]

딱히 특이한점이 없는 문제...?

- 한번에 나무가 번식함에 주의하여 빈배열을 따로 만들어서 해결

- for문 이내 while문으로 지정된 대각선 방향으로 계속 전진

- 제초제 기한 배열을 만들어 현재가 몇번째 년도인지 동기화시키고, 해당 년수때 제초제 제거

- 이전년도 문제로 갈수록 조금씩 쉬워지는거 같기도..... 낼...화이팅!

 

#include <iostream>
#include <vector>

using namespace std;
int N, M, K, C;
int board[21][21];
int side_board[21][21];
int finish[21][21];
int global_t;
int global_sum;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };//하,우,상,좌
int dx1[4] = { 1,1,-1,-1 };
int dy1[4] = { 1,-1,1,-1 };//하,우,상,좌


void grow(int x, int y) {
	int count = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (board[nx][ny] > 0)
			count++;
	}
	board[x][y] += count;
}
void side_grow(int x, int y) {
	int count = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		if (board[nx][ny] == 0)
			count++;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		if (board[nx][ny] == 0)
			side_board[nx][ny] += (board[x][y] / count);
	}
}
void check_most() {
	int pre_sum = 0;
	int max_x = 0;
	int max_y = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] > 0)
			{
				int sum = board[i][j];

				for (int k = 0; k < 4; k++)
				{
					int cur_x = i;
					int cur_y = j;
					int t=0;
					while (true) { //조건은 두가지:벽or제초제 아니면 k만큼 전파
						if (t == K) break;
						int nx = cur_x + dx1[k];
						int ny = cur_y + dy1[k];
						if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;
						if (board[nx][ny] <= 0)break;
						else if (board[nx][ny] > 0) {
							sum += board[nx][ny];
						}
						cur_x = nx;
						cur_y = ny;
						t++;
					}
				}
				if (pre_sum < sum) {
					max_x = i;
					max_y = j;
					pre_sum = sum;
				}

			}
		}
	}
	global_sum += pre_sum;
	board[max_x][max_y] = -1;
	finish[max_x][max_y] = global_t + C;
	for (int k = 0; k < 4; k++)
	{
		int cur_x = max_x;
		int cur_y = max_y;
		int t = 0;
		while (true) { //조건은 두가지:벽or제초제 아니면 k만큼 전파
			if (t == K) break;
			int nx = cur_x + dx1[k];
			int ny = cur_y + dy1[k];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;
			if (board[nx][ny] < 0 && finish[nx][ny] == 0) break;
			else if (board[nx][ny] == 0) {
				finish[nx][ny] = global_t + C;
				board[nx][ny] = -1;
				break;
			}
			else if (board[nx][ny] > 0) {
				finish[nx][ny] = global_t + C;
				board[nx][ny] = -1;
			}
			else if (board[nx][ny] < 0 && finish[nx][ny] != 0) {
				finish[nx][ny] = global_t + C;
				break;
			}
			cur_x = nx;
			cur_y = ny;
			t++;
		}
	}
	



}



int main(){
	cin >> N >> M >> K >> C;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}

	}
	global_t = 1;
	while (true) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				side_board[i][j] = 0; //초기화 
				if (board[i][j] > 0)
					grow(i, j);
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] > 0)
				{
					side_grow(i, j);
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] += side_board[i][j];
			}
		}
		check_most();
		if (global_t == M) break;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (finish[i][j] == global_t)
				{
					board[i][j] = 0;
					finish[i][j] = 0;
				}
			}
		}

		global_t++;
	}
	cout << global_sum;


}