나무박멸

삼성 2022 상반기 오후 기출2번 

0KB, 21ms

 

https://www.codetree.ai/frequent-problems/tree-kill-all/description

 

• BFS + 구현
• 주의점
  • 벽이 있거나 나무가 없어도 스프레이는 뿌려야한다.

#include <iostream>
#include <queue>
#include <iomanip>

#define MAX 20
using namespace std;

int map[MAX][MAX] = {}, spray[MAX][MAX] = {};
int N, M, K, C;

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

int answer = 0;

typedef struct tree {
	int y, x;
	int k;
	int dir;
}TREE;

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

void grow() {
	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (spray[i][j] > 0) spray[i][j]--;
			if (map[i][j] <= 0) continue;
			int cnt = 0;
			for (int p = 0; p < 4; p++) {
				int y = i + dy[p], x = j + dx[p];
				if (y >= N || x >= N || y < 0 || x < 0) continue;

				if (map[y][x] > 0) cnt++;
			}
			map[i][j] += cnt;
		}
}

void spread() {
	int copy[MAX][MAX] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			copy[i][j] = map[i][j];

	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (copy[i][j] <= 0) continue;
			
			int cnt = 0, y, x;
			for (int p = 0; p < 4; p++) { // 1600
				y = i + dy[p]; x = j + dx[p];
				if (y >= N || x >= N || y < 0 || x < 0 
					|| spray[y][x] > 0) continue;

				if (copy[y][x] == 0) cnt++;
			}

			for (int p = 0; p < 4; p++) {
				y = i + dy[p]; x = j + dx[p];
				if (y >= N || x >= N || y < 0 || x < 0 || spray[y][x] > 0) continue;

				if (copy[y][x] == 0) map[y][x] += copy[i][j] / cnt;
			}
		}
}

pair<int, int> get_spray() {
	pair<int,int> res;
	int res_num = -1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] <= 0) continue;

			bool visited[MAX][MAX] = {};
			int num = 0; 
			queue<TREE> q;

			visited[i][j] = true;
			num += map[i][j];

			q.push({ i, j, 0, 0 });
			q.push({ i, j, 0, 1 });
			q.push({ i, j, 0, 2 });
			q.push({ i, j, 0, 3 });

			while (!q.empty()) {
				TREE now = q.front(); q.pop();
				if (now.k == K) continue;

				int new_y = now.y + dyy[now.dir], new_x = now.x + dxx[now.dir];
				if (new_y >= N || new_x >= N 
					|| new_y < 0 || new_x < 0 
					|| visited[new_y][new_x]
					|| map[new_y][new_x] <= 0) continue;

					visited[new_y][new_x] = true;
					num += map[new_y][new_x];
					q.push({new_y, new_x, now.k+1, now.dir});
			}

			if (res_num < num) {
				res_num = num;
				res = { i, j };
			}
		}
	}

	if (res_num == -1) res = { 0,0 };

	return res;
}

void set_spray(pair<int, int> ch) {
	int y = ch.first, x = ch.second;
	bool visited[MAX][MAX] = {};
	queue<TREE> q;

	if (map[y][x] <= 0) {
		spray[y][x] = C + 1;
		return;
	}

	visited[y][x] = true;
	q.push({ y, x, 0, 0 });
	q.push({ y, x, 0, 1 });
	q.push({ y, x, 0, 2 });
	q.push({ y, x, 0, 3 });
	answer += map[y][x];
	map[y][x] = 0;
	spray[y][x] = C + 1;
	
	while (!q.empty()) {
		TREE now = q.front(); q.pop();
		if (now.k == K) continue;

		int new_y = now.y + dyy[now.dir], new_x = now.x + dxx[now.dir];
		if (new_y >= N || new_x >= N
			|| new_y < 0 || new_x < 0
			|| visited[new_y][new_x]) continue;

		if (map[new_y][new_x] <= 0) {
			spray[new_y][new_x] = C + 1;
			continue;
		}

		visited[new_y][new_x] = true;
		answer += map[new_y][new_x];
		map[new_y][new_x] = 0;
		spray[new_y][new_x] = C + 1;
		q.push({ new_y, new_x, now.k + 1, now.dir });
	}
}

void solve() {
	while (M--) {
		grow();
		spread();
		
		pair<int, int> choice = get_spray();
		set_spray(choice);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	solve();

	cout << answer;

	return 0;
}