Written by Daeyeol Sung
[ Algorithm ] 백준 나무 재테크 (16235번)
오늘 풀이 할 문제는 백준 나무 재테크 문제이다. 백준 삼성 SW 역량 테스트 기출 문제 문제집에 있는 문제이다. 문제에서 봄, 여름, 가을, 겨울에 각각 수행 할 내용을 나눠서 알려주기 때문에 비교적 어렵지 않은 문제였다.
문제
문제는 여기에 참조한다.
풀이
상도가 가지고 있는 n x n 땅에는 초기 양분이 5씩 들어있고, S2D2라는 로봇이 겨울에 돌아다니면서 각 칸에 정해진 양의 양분을 추가한다고 한다. 현재 각 칸에에 존재하는 양분의 양을 저장할 이차원 배열 land와, 겨울이 되면 각 칸에 추가되는 양분의 양을 저장할 이차원 배열 A를 만들고 입력을 받아 초기화 해줬다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
land = new int[n+1][n+1];
A = new int[n+1][n+1];
// 땅의 처음 양분과 추가되는 양분 초기화
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
land[i][j] = 5;
A[i][j] = Integer.parseInt(st.nextToken());
}
}
다음 입력으로는 상도가 나무를 심은 칸의 위치와 나무의 나이가 주어지는데 나무는 위치와 나이를 가지고 있는 객체로 만들어서 사용하기 위해 클래스를 정의했고 이 나무를 저장할 자료구조로 우선순위 큐를 선택했다. 우선순위 큐는 나무의 나이가 오름차순이 되도록 정렬한다.
// 현재 땅에 존재하는 나무(나이 오름차순으로 정렬)
PriorityQueue<Tree> trees = new PriorityQueue<>(new Comparator<>() {
public int compare(Tree t1, Tree t2) {
return t1.age - t2.age;
}
});
// 처음 땅에 심은 나무를 저장
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
trees.offer(new Tree(x, y, age));
}
private static class Tree {
private int x;
private int y;
private int age;
Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
}
이제 봄, 여름, 가을, 겨울 메소드를 만들고 각각 구현한다.
우선 봄에는 나무가 자신의 칸에 있는 양분을 자신의 나이만큼 먹고 나이가 1이 증가하거나 양분을 먹지 못해 죽는다고 한다. 한 칸에는 나무가 여러개 있을 수 있고 이런 경우에는 나이가 적은 나무가 먼저 양분을 먹는다고 한다. 이 부분이 나무를 저장할 자료구조로 우선순위 큐를 선택하고 나이가 오름차순이 되도록 정렬한 이유이다. 양분을 먹고 나이가 증가한 나무와 양분을 먹지 못하고 죽은 나무로 분리해서 저장하고 살아남은 나무들은 다시 우선순위 큐에 추가하고 죽은 나무들은 따로 반환한다.
private static List<Tree> spring(PriorityQueue<Tree> trees) {
// 죽은 나무와 살아남은 나무를 저장할 리스트
List<Tree> deadTrees = new ArrayList<>();
List<Tree> aliveTrees = new ArrayList<>();
while(!trees.isEmpty()) {
Tree tree = trees.poll();
// 땅의 양분이 나무의 나이 이상이어야 나무가 양분을 먹음
if(land[tree.x][tree.y] >= tree.age) {
aliveTrees.add(new Tree(tree.x, tree.y, tree.age+1));
land[tree.x][tree.y] -= tree.age;
}
// 땅의 양분이 나무의 나이보다 작다면 나무가 죽음
else {
deadTrees.add(tree);
}
}
// 살아남은 나무들을 우선순위 큐에 추가하고 죽은 나무 리스트를 반환
for(Tree tree : aliveTrees) {
trees.offer(tree);
}
return deadTrees;
}
여름에는 봄에 죽은 나무들이 양분으로 바뀌어 나무가 있던 칸에 추가된다고 한다. 추가되는 양분은 나무의 나이 / 2 이다. 봄에 죽은 나무들을 전달받아 나무가 있던 칸에 양분을 추가한다.
private static void summer(List<Tree> deadTrees) {
// 죽은 나무들이 양분으로 변함
for(Tree tree : deadTrees) {
land[tree.x][tree.y] += tree.age / 2;
}
}
가을에는 나이가 5의 배수인 나무들이 번식한다고 한다. 상도가 가지고 있는 n x n 땅을 벗어나지 않는 범위에서 인접한 8칸에 나이가 1인 나무가 새로 생긴다. 새로 생긴 나무들은 우선수위 큐에 추가한다.
private static void fall(PriorityQueue<Tree> trees) {
// 번식하여 새로 생기는 나무 리스트
List<Tree> newTrees = new ArrayList<>();
for(Tree tree : trees) {
// 나무의 나이가 5의 배수이면서
if(tree.age % 5 == 0) {
for(int i = 0; i < dirs.length; i++) {
int nx = tree.x + dirs[i][0];
int ny = tree.y + dirs[i][1];
// 땅을 벗어나지 않는 경우 새로 생길 수 있음
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
newTrees.add(new Tree(nx, ny, 1));
}
}
}
}
// 새로 생긴 나무들을 우선순위 큐에 추가
for(Tree tree : newTrees) {
trees.offer(tree);
}
}
겨울에는 S2D2가 땅에 새로운 양분을 추가한다. 처음에 입력 받았던 추가되는 양분을 각 칸에 추가한다.
private static void winter() {
// S2D2가 땅을 돌아다니면서 땅에 양분을 추가
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
land[i][j] += A[i][j];
}
}
}
마지막으로 전체 코드이다.
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[][] land;
static int[][] A;
static int[][] dirs = new int[][] {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {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());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
land = new int[n+1][n+1];
A = new int[n+1][n+1];
// 땅의 처음 양분과 추가되는 양분 초기화
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= n; j++) {
land[i][j] = 5;
A[i][j] = Integer.parseInt(st.nextToken());
}
}
// 현재 땅에 존재하는 나무(나이 오름차순으로 정렬)
PriorityQueue<Tree> trees = new PriorityQueue<>(new Comparator<>() {
public int compare(Tree t1, Tree t2) {
return t1.age - t2.age;
}
});
// 처음 땅에 심은 나무를 저장
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
trees.offer(new Tree(x, y, age));
}
// k년 동안 반복
for(int i = 0; i < k; i++) {
List<Tree> deadTrees = spring(trees);
summer(deadTrees);
fall(trees);
winter();
}
System.out.println(trees.size());
}
private static List<Tree> spring(PriorityQueue<Tree> trees) {
// 죽은 나무와 살아남은 나무를 저장할 리스트
List<Tree> deadTrees = new ArrayList<>();
List<Tree> aliveTrees = new ArrayList<>();
while(!trees.isEmpty()) {
Tree tree = trees.poll();
// 땅의 양분이 나무의 나이 이상이어야 나무가 양분을 먹음
if(land[tree.x][tree.y] >= tree.age) {
aliveTrees.add(new Tree(tree.x, tree.y, tree.age+1));
land[tree.x][tree.y] -= tree.age;
}
// 땅의 양분이 나무의 나이보다 작다면 나무가 죽음
else {
deadTrees.add(tree);
}
}
// 살아남은 나무들을 우선순위 큐에 추가하고 죽은 나무 리스트를 반환
for(Tree tree : aliveTrees) {
trees.offer(tree);
}
return deadTrees;
}
private static void summer(List<Tree> deadTrees) {
// 죽은 나무들이 양분으로 변함
for(Tree tree : deadTrees) {
land[tree.x][tree.y] += tree.age / 2;
}
}
private static void fall(PriorityQueue<Tree> trees) {
// 번식하여 새로 생기는 나무 리스트
List<Tree> newTrees = new ArrayList<>();
for(Tree tree : trees) {
// 나무의 나이가 5의 배수이면서
if(tree.age % 5 == 0) {
for(int i = 0; i < dirs.length; i++) {
int nx = tree.x + dirs[i][0];
int ny = tree.y + dirs[i][1];
// 땅을 벗어나지 않는 경우 새로 생길 수 있음
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
newTrees.add(new Tree(nx, ny, 1));
}
}
}
}
// 새로 생긴 나무들을 우선순위 큐에 추가
for(Tree tree : newTrees) {
trees.offer(tree);
}
}
private static void winter() {
// S2D2가 땅을 돌아다니면서 땅에 양분을 추가
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
land[i][j] += A[i][j];
}
}
}
private static class Tree {
private int x;
private int y;
private int age;
Tree(int x, int y, int age) {
this.x = x;
this.y = y;
this.age = age;
}
}
}