삼성 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;
}'coding > baekjoon_codingstudy' 카테고리의 다른 글
| 20058 마법사 상어와 파이어스톰 (0) | 2022.10.12 |
|---|---|
| 21608 상어 초등학교 (0) | 2022.10.11 |
| 21610 마법사 상어와 비바라기 (0) | 2022.10.11 |
| 20057 마법사 상어와 토네이도 (0) | 2022.10.10 |
| 17825 주사위 윷놀이 (0) | 2022.10.10 |