[백준] 16235번: 나무재테크 문제 풀이

https://www.acmicpc.net/problem/16235

자료구조 및 메서드 선언

이번 문제에서는 필요한 자료구조가 조금 많았다.
살아있는 나무, 죽은 나무, 번식된 나무의 정보를 저장할 리스트들이 필요했는데, 간편하에 ArrayDeque로 통일하여 생성하였다.
또한 각 칸마다 영양분을 담을 2차원 배열과, 각 칸마다 매년 겨울 추가할 영양분을 담을 2차원 배열을 생성하였다.
마지막으로 나무를 번식시키기 위한 8가지 방향을 담은 dx, dy 배열을 생성해주었다.

// 나무들의 정보를 담을 자료구조
static ArrayDeque<int []> woods = new ArrayDeque<>();
// 죽은 나무들의 정보를 담을 자료구조
static ArrayDeque<int []> deadWoods = new ArrayDeque<>();
// 번식된 나무들의 정보를 담을 자료구조
static ArrayDeque<int []> babyWoods = new ArrayDeque<>();
// 각 땅에 저장된 영양분을 담을 배열
static int ground[][];
// 각 땅에 추가할 영양분을 담을 배열
static int nutrient[][];
// 8방향
static int [] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
static int [] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
static int N;

매 년 계절마다 각각 특정 기능을 수행해야하기에 봄, 여름, 가을, 겨울 4개의 메서드로 나눠주었다.

for (int i = 0; i < K; i++) {
	spring();
	summer();
	fall();
	winter();
}

---

영양분의 값 입력

N * N번씩 반복하면서 추가 영양분의 정보를 입력받는다.
동시에 현재 땅의 영양분의 양을 5로 초기화한다.

for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < N; j++) {
		nutrient[i][j] = Integer.parseInt(st.nextToken());
		ground[i][j] = 5;
	}
}

---

현재 심어진 나무 정보 입력

현재 심어진 나무의 위치, 나이를 1차원 배열로 만들어 woods에 저장한다.

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());
	woods.offer(new int [] {x-1, y-1, age});
}

---

봄

현재 심어져있는 나무들의 수만큼 반복한다.
나이가 어린 나무부터 양분을 흡수하기 때문에 나무의 정보를 woods의 뒤에서부터 꺼낸다
(가을에 번식된 새끼 나무들은 woods에 뒤에 추가할 예정)
꺼낸 나무의 위치에 있는 양분의 양이 나무의 나이보다 많으면, 나무의 나이를 1씩 증가시키고, 해당 땅에 저장된 양분의 양을 나이만큼 감소시킨다.
그리고 꺼낸 나무는 다시 ArrayDeque에 맨 앞에 넣는다.
(나이가 어린 나무를 자연스레 맨 뒤에 배치하기 위해)
만약 나무의 나이가 영양분보다 많다면 deadWoods에 삽입한다.

static void spring() {
	for (int i = 0; i < woods.size();) {
      int [] wood = woods.pollLast();
      int x = wood[0];
      int y = wood[1];
      int age = wood[2];
      if (ground[x][y] >= age) {
          ground[x][y] -= age;
          wood[2] += 1;
          i++;
          woods.addFirst(wood);
      }
      else deadWoods.offer(wood);
	}
}

---

여름

죽은 나무들이 양분이 되는 메서드이다.
죽은 나무들이 더이상 없을 때까지 나무를 꺼내 각 위치에 해당하는 땅에 영양분을 추가한다.

static void summer() {
	while (!deadWoods.isEmpty()) {
		int [] wood = deadWoods.poll();
		int x = wood[0];
		int y = wood[1];
		int age = wood[2];
		ground[x][y] += age/2;
	}
}

---

가을

나무들이 번식하는 메서드이다.
현재 심어진 나무들만큼 반복하면서 나무들을 꺼낸다.
현재 꺼낸 나무의 나이가 5로 나누어 떨어지면 주변 8칸을 검사하여 번식할 수 있는지 검사한다.
번식할 수 있다면 번식된 나무는 babyWoods에 삽입한다.
꺼냈던 나무는 다시 ArrayDeque 뒤에 삽입한다.

번식이 끝났으면 번식된 나무들을 Woods의 뒤에 삽입한다.
(봄에 나이가 어린 나무부터 양분을 흡수시키기 위해 어린 나무들은 모두 뒤쪽에 배치)

static void fall() {
	for (int i = 0 ; i < woods.size(); i++) {
		int [] wood = woods.poll();
		int x = wood[0];
		int y = wood[1];
		int age = wood[2];
		if (age % 5 == 0) {
			for (int j = 0; j < 8; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (0 <= nx && nx < N && 0 <= ny && ny < N)
					babyWoods.offer(new int [] {nx, ny, 1});
			}
		}
		woods.offer(wood);
	}
	while (!babyWoods.isEmpty())
		woods.offer(babyWoods.poll());
}

---

겨울

각 칸에 영양분을 추가한다.

static void winter() {
	for (int i = 0; i < N; i++ ) 
		for (int j = 0; j < N; j++)
			ground[i][j] += nutrient[i][j];
}

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static ArrayDeque<int []> woods = new ArrayDeque<>();
	static ArrayDeque<int []> deadWoods = new ArrayDeque<>();
	static ArrayDeque<int []> babyWoods = new ArrayDeque<>();
	static int ground[][];
	static int nutrient[][];
	static int [] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int [] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int N;
	
	static void spring() {
		for (int i = 0; i < woods.size();) {
			int [] wood = woods.pollLast();
			int x = wood[0];
			int y = wood[1];
			int age = wood[2];
			if (ground[x][y] >= age) {
				ground[x][y] -= age;
				wood[2] += 1;
				i++;
				woods.addFirst(wood);
			}
			else deadWoods.offer(wood);
		}
	}
	
	static void summer() {
		while (!deadWoods.isEmpty()) {
			int [] wood = deadWoods.poll();
			int x = wood[0];
			int y = wood[1];
			int age = wood[2];
			ground[x][y] += age/2;
		}
	}
	
	static void fall() {
		for (int i = 0 ; i < woods.size(); i++) {
			int [] wood = woods.poll();
			int x = wood[0];
			int y = wood[1];
			int age = wood[2];
			if (age % 5 == 0) {
				for (int j = 0; j < 8; j++) {
					int nx = x + dx[j];
					int ny = y + dy[j];
					if (0 <= nx && nx < N && 0 <= ny && ny < N)
						babyWoods.offer(new int [] {nx, ny, 1});
				}
			}
			woods.offer(wood);
		}
		while (!babyWoods.isEmpty())
			woods.offer(babyWoods.poll());
	}
	
	static void winter() {
		for (int i = 0; i < N; i++ ) 
			for (int j = 0; j < N; j++)
				ground[i][j] += nutrient[i][j];
	}
	
	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());
		ground = new int [N][N];
		nutrient = new int [N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				nutrient[i][j] = Integer.parseInt(st.nextToken());
				ground[i][j] = 5;
			}
		}
		
		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());
			woods.offer(new int [] {x-1, y-1, age});
		}
		
		for (int i = 0; i < K; i++) {
			spring();
			summer();
			fall();
			winter();
		}
		
		System.out.println(woods.size());
	}
}