알고리즘(종합)/Lv.3
코드트리 - 나무박멸(시뮬레이션)
ch.0
2023. 4. 7. 23:47
문제 분석
// 0. 나무 성장하기
// 1. 나무 퍼지기
// 2. 제거할 나무 선정하기
// 3. 제거한 나무 점수 확인
// 4. 제초제 뿌리기 다른 배열 선언해서 -1 해주기
크게 5개로 분할하였고
2, 3 번을 하나의 메서드로 만들었다.
문제는 직관적으로 풀어나갔다.
1. 4방향에 나무가 있는 만큼 +점수
2. 4방향으로 제초제가 뿌려지지 않았으며 벽이 아닐경우 나무가 퍼져나가게 했다.
3. 제초제 범위만큼의 대각선으로 점수를 합하여 선정했다.
4. 제초제를 다른 배열로 선언하여 저장하였다.
전체 소스
package test;
import java.util.*;
import java.io.*;
public class Main {
public static int size, year, rage, using;
public static final int max_size = 20;
public static int[][] array;
public static int[][] next_array;
public static int[][] medic = new int[max_size][max_size];
public static int[] remove_point = new int[2];
// 0. 나무 성장하기
// 1. 나무 퍼지기
// 2. 제거할 나무 선정하기
// 3. 제거한 나무 점수 확인
// 4. 제초제 뿌리기 다른 배열 선언해서 -1 해주기
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static int[] ddx = { -1, -1, 1, 1 };
public static int[] ddy = { -1, 1, 1, -1 };
public static boolean over(int x, int y) {
return x >= 0 && y >= 0 && x < size && y < size;
}
public static void clone_array() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
array[i][j] = next_array[i][j];
}
}
}
public static void print() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println("--------------------------");
}
// 0. 나무 성장하기
public static void tree_grow() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (array[i][j] > 0) {
int cnt = 0;
for (int p = 0; p < 4; p++) {
int mx = i + dx[p];
int my = j + dy[p];
if (over(mx, my) && array[mx][my] > 0) {
cnt++;
}
}
array[i][j] += cnt;
}
}
}
}
// 1. 나무 퍼지기
public static void tree_virous() {
next_array = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (array[i][j] == -1) {
next_array[i][j] = -1;
}
if (array[i][j] > 0) {
int cnt = 0;
next_array[i][j] = array[i][j];
for (int p = 0; p < 4; p++) {
int mx = i + dx[p];
int my = j + dy[p];
if (over(mx, my) && array[mx][my] == 0 && medic[mx][my] == 0) {
cnt++;
}
}
for (int p = 0; p < 4; p++) {
int mx = i + dx[p];
int my = j + dy[p];
if (over(mx, my) && array[mx][my] == 0 && medic[mx][my] == 0) {
next_array[mx][my] += (array[i][j] / cnt);
}
}
}
}
}
// 완료후 배열 복사
clone_array();
}
// 2. 제거할 나무 선정 + 3. 점수
public static int remove_tree() {
int result = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (array[i][j] > 0) {
int score = array[i][j];
for (int p = 0; p < 4; p++) {
int mx = i;
int my = j;
for (int t = 0; t < rage; t++) {
mx = mx + ddx[p];
my = my + ddy[p];
if (over(mx, my)) {
if (array[mx][my] == 0) {
break;
} else if (array[mx][my] == -1) {
break;
}
score += array[mx][my];
}
}
}
if (result < score) {
result = score;
remove_point[0] = i;
remove_point[1] = j;
// 0,0 부터 체크해서 사실상 의미는 없지만 조건에 주어졌으니 추가했다.
} else if (result == score) {
if (remove_point[0] > i) {
remove_point[0] = i;
remove_point[1] = j;
} else if (remove_point[0] == i) {
remove_point[1] = Math.min(remove_point[1], j);
}
}
}
}
}
return result;
}
// 4. 제초제 뿌리기
public static void spray() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (medic[i][j] > 0) {
--medic[i][j];
}
}
}
for (int p = 0; p < 4; p++) {
int mx = remove_point[0];
int my = remove_point[1];
for (int t = 0; t < rage; t++) {
mx = mx + ddx[p];
my = my + ddy[p];
if (over(mx, my)) {
medic[mx][my] = using;
if (array[mx][my] == 0) {
break;
} else if (array[mx][my] == -1) {
medic[mx][my] = -1;
break;
}
array[mx][my] = 0;
}
}
}
array[remove_point[0]][remove_point[1]] = 0;
medic[remove_point[0]][remove_point[1]] = using;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
size = Integer.parseInt(st.nextToken());
year = Integer.parseInt(st.nextToken());
rage = Integer.parseInt(st.nextToken());
using = Integer.parseInt(st.nextToken());
array = new int[size][size];
next_array = new int[size][size];
for (int i = 0; i < size; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < size; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
}
}
int result = 0;
for (int t = 0; t < year; t++) {
// print();
tree_grow();
// print();
tree_virous();
// print();
result += remove_tree();
spray();
}
System.out.println(result);
}
}
문제
문제는 저작권이 염려되어 올리지 않았다.
코드트리 사이트(https://www.codetree.ai/missions)에 들어가면 무료로 제공하고 있다.