All :L
[BOJ/Java] 나무 재테크 (16235) 본문
반응형
1. 문제 분석
문제 개요
- 나무 재테크 문제는 N x N 크기의 땅에 나무를 심고, 주어진 조건에 따라 나무를 키워나가며, K년이 지난 후 살아남은 나무의 개수를 구하는 문제이다.
- 계절에 따라 나무의 성장, 죽음, 번식, 그리고 땅의 양분이 추가되는 과정이 주어지며, 이를 시뮬레이션으로 해결해야 한다.
입력 형식
- 첫 번째 줄에는
N(땅의 크기),M(처음 심어진 나무의 개수),K(몇 년 후까지 볼 것인지) 주어진다. - 그다음
N개의 줄에 각 칸에 추가되는 양분의 양이 주어진다. - 그다음
M개의 줄에 나무의 위치와 나이 정보가 주어진다.
출력 형식
K년 후에 살아남은 나무의 개수를 출력한다.
2. 알고리즘 종류
- 시뮬레이션: 계절별로 주어진 규칙에 따라 나무의 상태를 변화시켜 시뮬레이션을 진행한다.
- 우선순위 큐(Priority Queue): 나이가 어린 나무가 먼저 양분을 흡수해야 하므로, 나무의 나이를 기준으로 정렬이 필요하다.
3. 주요 부분 및 코드 작성 방법
1. 초기화
- 땅의 크기
N, 나무의 개수M, 몇 년 동안 진행할 것인지K를 입력받는다. - 각 칸에 추가되는 양분의 양을 입력받고, 처음에 모든 칸의 양분을 5로 초기화한다.
2. 나무의 성장 및 죽음
- 봄: 각 나무는 자신의 나이만큼 땅의 양분을 먹고 나이가 1씩 증가한다. 만약 나무가 충분한 양분을 얻지 못하면 그 나무는 죽는다.
- 여름: 봄에 죽은 나무들은 양분이 되어 그 자리에 다시 반환된다. 죽은 나무의 나이 절반만큼 양분이 추가된다.
3. 나무의 번식
- 가을: 나무의 나이가 5의 배수인 경우, 인접한 8방향에 새로운 나무가 생긴다. 번식된 나무는 나이가 1이다.
4. 양분 추가
- 겨울: 각 칸에 주어진 양분을 추가한다.
4. 코드 설명
(1) 메인 함수 (main)
초기화 및 입력 처리
N = Integer.parseInt(st.nextToken()); // 땅의 크기 M = Integer.parseInt(st.nextToken()); // 나무의 개수 K = Integer.parseInt(st.nextToken()); // 몇 년 동안 진행할지- 땅의 크기
N, 나무의 개수M, 몇 년 동안 진행할지K를 입력받는다.
- 땅의 크기
땅의 양분 정보 및 나무 정보 입력
for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { A[i][j] = Integer.parseInt(st.nextToken()); // 추가될 양분의 양 grid[i][j] = 5; // 초기 양분은 5 } } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()) - 1; int y = Integer.parseInt(st.nextToken()) - 1; int z = Integer.parseInt(st.nextToken()); // 나무의 나이 plant.add(new Tree(x, y, z)); // 나무 리스트에 추가 }A배열에 양분 정보를 입력받고, 각 칸의 초기 양분을 5로 설정한다.- 나무의 위치와 나이를 받아
Tree객체로 저장한다.
시뮬레이션 실행
for (int i = 0; i < K; i++) { spring(); // 봄 summer(); // 여름 fall(); // 가을 winter(); // 겨울 Collections.sort(plant, (o1, o2) -> o1.age - o2.age); // 나이순으로 정렬 } System.out.println(plant.size()); // K년 후 살아남은 나무의 개수 출력K년 동안 봄, 여름, 가을, 겨울의 시뮬레이션을 차례로 실행한다.
(2) 계절별 함수 구현
spring 함수: 봄에는 나무가 자신의 나이만큼 양분을 먹고 나이가 1씩 증가한다. 만약 양분이 부족하면 그 나무는 죽는다.
public static void spring() { for (int i = 0; i < plant.size(); i++) { Tree tree = plant.get(i); if (grid[tree.x][tree.y] < tree.age) { // 양분 부족하면 나무 죽음 deadTree.add(i); // 죽은 나무 인덱스 저장 } else { grid[tree.x][tree.y] -= tree.age; // 양분 흡수 tree.age++; // 나이 증가 } } }summer 함수: 여름에는 죽은 나무가 양분이 되어 땅에 반환된다.
public static void summer() { while (!deadTree.isEmpty()) { Tree tree = plant.get(deadTree.poll()); // 죽은 나무 처리 grid[tree.x][tree.y] += (tree.age / 2); // 죽은 나무가 양분으로 변환 tree.deadTree = true; // 나무 상태를 죽은 나무로 표시 } }fall 함수: 가을에는 나무가 번식한다. 나이가 5의 배수인 나무는 인접한 8방향으로 번식한다.
public static void fall() { for (int i = 0; i < plant.size(); i++) { Tree tree = plant.get(i); if (tree.deadTree) continue; // 죽은 나무는 번식하지 않음 if (tree.age % 5 == 0) { // 나이가 5의 배수인 나무 번식 for (int d = 0; d < 8; d++) { int nr = tree.x + dr[d]; int nc = tree.y + dc[d]; if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue; // 범위 체크 plant.add(new Tree(nr, nc, 1)); // 새로운 나무 추가 } } } // 죽은 나무 제거 ArrayList<Tree> newTree = new ArrayList<>(); for (Tree tree : plant) { if (tree.deadTree) continue; newTree.add(tree); } plant = newTree; }winter 함수: 겨울에는 각 칸에 주어진 양분을 추가한다.
public static void winter() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { grid[i][j] += A[i][j]; // 추가 양분 더함 } } }
5. 전체 코드
package BOJ.Day0924.BOJ나무_재테크;
import java.io.*;
import java.util.*;
public class BOJ16235 {
static int N, M, K; // 땅의 크기, 나무의 개수, 몇 년 동안 진행할지
static int[][] grid, A; // 땅의 양분 상태, 추가 양분 정보
static ArrayList<Tree> plant = new ArrayList<>(); // 나무 리스트
static Queue<Integer> deadTree = new LinkedList<>(); // 죽은 나무의 인덱스
static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1}; // 8방향
static int[] dc = {0, 0, -1, 1, -
1, 1, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 땅의 크기
M = Integer.parseInt(st.nextToken()); // 나무의 개수
K = Integer.parseInt(st.nextToken()); // 몇 년 동안 진행할지
grid = new int[N][N];
A = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
A[i][j] = Integer.parseInt(st.nextToken()); // 추가 양분 정보
grid[i][j] = 5; // 처음 땅의 양분은 5
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
int z = Integer.parseInt(st.nextToken()); // 나무의 나이
plant.add(new Tree(x, y, z)); // 나무 추가
}
Collections.sort(plant, (o1, o2) -> o1.age - o2.age); // 나이순으로 정렬
for (int i = 0; i < K; i++) {
spring(); // 봄
summer(); // 여름
fall(); // 가을
winter(); // 겨울
Collections.sort(plant, (o1, o2) -> o1.age - o2.age); // 나이순으로 재정렬
}
System.out.println(plant.size()); // K년 후 살아남은 나무의 개수 출력
}
// 봄: 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 양분이 부족하면 죽는다.
public static void spring() {
for (int i = 0; i < plant.size(); i++) {
Tree tree = plant.get(i);
if (grid[tree.x][tree.y] < tree.age) { // 양분이 부족하면
deadTree.add(i); // 죽은 나무 인덱스 추가
} else {
grid[tree.x][tree.y] -= tree.age; // 양분 흡수
tree.age++; // 나이 증가
}
}
}
// 여름: 죽은 나무가 양분이 되어 땅으로 돌아간다.
public static void summer() {
while (!deadTree.isEmpty()) {
Tree tree = plant.get(deadTree.poll()); // 죽은 나무 처리
grid[tree.x][tree.y] += (tree.age / 2); // 죽은 나무의 나이 절반이 양분으로 변환
tree.deadTree = true; // 나무 상태를 죽은 나무로 표시
}
}
// 가을: 나이가 5의 배수인 나무가 번식한다.
public static void fall() {
for (int i = 0; i < plant.size(); i++) {
Tree tree = plant.get(i);
if (tree.deadTree) continue; // 죽은 나무는 번식하지 않음
if (tree.age % 5 == 0) { // 나이가 5의 배수인 나무 번식
for (int d = 0; d < 8; d++) {
int nr = tree.x + dr[d];
int nc = tree.y + dc[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue; // 범위 체크
plant.add(new Tree(nr, nc, 1)); // 새로운 나무 추가
}
}
}
// 죽은 나무 제거
ArrayList<Tree> newTree = new ArrayList<>();
for (Tree tree : plant) {
if (tree.deadTree) continue;
newTree.add(tree);
}
plant = newTree;
}
// 겨울: 각 칸에 주어진 양분을 추가한다.
public static void winter() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] += A[i][j]; // 양분 추가
}
}
}
}
// 나무 클래스
class Tree {
int x, y, age;
boolean deadTree; // 나무가 죽었는지 여부
Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
}반응형
Comments