오늘 풀어볼 문제는 나무 재테크 라는 문제이다.
1. 문제요약
-
N * N 크기의 땅이 있고, 각 땅에는 초기에 5만큼의 양분이 있다.
-
나무는 사계절을 보내며 다음과 같은 과정을 거친다.
-
봄
- 나무가 자신의 나이만큼 현재 위치한 땅의 양분을 먹고, 나이가 1 증가한다.
- 하나의 칸에 여러 나무가 있다면, 가장 어린 나무부터 양분을 먹는다.
- 나이만큼 먹을 양분이 부족하다면 해당 나무는 양분을 흡수하지 않고 바로 죽는다.
-
여름
- 봄에 죽은 나무가 양분으로 변한다. (해당 나무 나이 / 2)
-
가을
- 나이가 5의 배수인 나무들만 번식한다. 인접한 8개의 칸에 나이가 1인 나무를 추가한다.
-
겨울
- 땅에 양분을 추가한다. 추가되는 양분의 양은 입력값으로 주어진다.
-
K년이 지난 후, 살아있는 나무의 개수를 구하라.
2. 입출력
[입력]
- 땅 크기 N, 나무 그루 수 M, 주어질 년 수 K 주어짐
- N개의 줄에 양분의 양이 주어짐. 매해 겨울마다 추가해줘야 함.
- 다음 M개의 줄에 나무의 정보 나타내는 X, Y, Z 주어짐 (위치 X,Y, 나이 Z)
3. 제한
- 1 ≤ N ≤ 10
- 1 ≤ K ≤ 1,000
- 1 ≤ A[r][c] ≤ 100
- 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
4. 시간
- 0.3초
5. 알고리즘
단순 빡구현
나무 관련 3개의 자료구조
- 죽은 나무 정보 담을 리스트1
- 새롭게 나이를 먹은 나무 정보 담을 리스트2
- 현재 나무의 생/사 결정 위한 정보 담을 우선순위큐1
땅 관련 2개의 배열
- 매 겨울마다 추가해줄 초기 입력값 양분 배열
- 매해마다 갱신되는 양분 배열
- 나이 순대로 우선순위큐에 나무 위치 저장.
- 해당 큐가 빌 때까지 돌림
2.1 해당 땅에 나무 나이만큼의 양분이 있다면, 해당 땅의 양분 줄인 후, 나무 나이 추가해 리스트2에 담음
2.2 없다면, 리스트1에 담음 - 리스트1에 담긴 나무들의 나이 / 2 만큼의 양분을 땅에 추가한다.
- 리스트1의 size만큼 돌린다.
4.1 나이가 5배수에 해당하는 나무들의 8개의 인접 땅에 1살 나무를 추가. - 입력값으로 주어졌던 양분을 땅에 더해준다.
위 과정을 k년만큼 반복한 후, 최종 리스트2의 크기를 반환한다.
6. 정답 코드
위 로직대로 코드를 짜니, 쉽게 정답을 맞출 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Info implements Comparable <Info> {
int x;
int y;
int age;
public Info(int x, int y, int age)
{
this.x=x;
this.y=y;
this.age=age;
}
@Override
public int compareTo(Info o){
return this.age-o.age;
}
}
public class Main {
static int N;
static int [][] GROUND;
static int [][] ENERGY;
static List<Info> DEAD;
static List<Info> LIVE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M, K;
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
ENERGY = new int[N+1][N+1];
GROUND = new int[N+1][N+1];
DEAD = new ArrayList<>();
LIVE = new ArrayList<>();
for(int i=1; i<=N; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++){
ENERGY[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());
LIVE.add(new Info(x, y, age));
}
while (K --> 0) {
spring();
summer();
fall();
winter();
}
System.out.println(LIVE.size());
}
static void spring() {
Queue<Info> pq = new PriorityQueue<>();
List<Info> tmp = new ArrayList<>();
for(int i=0; i<LIVE.size(); i++){
pq.add(LIVE.get(i));
}
while (!pq.isEmpty()) {
Info tree = pq.poll();
if(tree.age > GROUND[tree.x][tree.y]){
DEAD.add(tree);
continue;
}
GROUND[tree.x][tree.y]-=tree.age;
tree.age++;
tmp.add(tree);
}
LIVE = tmp;
}
static void summer(){
for(Info dead : DEAD){
GROUND[dead.x][dead.y] += (dead.age / 2);
}
DEAD = new ArrayList<>();
}
static void fall() {
int [][] dir = {{1,0}, {-1,0}, {0,1}, {0, -1}, {1,1}, {-1,-1}, {1,-1}, {-1,1}};
for(int i=0; i<LIVE.size(); i++) {
Info tree = LIVE.get(i);
if(tree.age % 5 != 0)
continue;
for(int j=0; j<8; j++) {
int nx = tree.x+dir[j][0];
int ny = tree.y+dir[j][1];
if(nx <= 0 || ny <= 0 || nx > N || ny > N)
continue;
LIVE.add(new Info(nx, ny, 1));
}
}
}
static void winter(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
GROUND[i][j] += ENERGY[i][j];
}
}
}
}
근데 메모리도, 시간도 너무너무너무 비효율적이었다.
그래서 가장 빠른 코드를 찾아봤는데, 나랑 정말 다른 접근법으로 푸셨길래 분석해봤다.
7. 다른 사람 풀이 코드
이 코드는 헤더 노드가 있는 원형 이중 연결리스트로 풀이한 버전이다.
코테 하면서 한 번도 이런 형태로 푼 적이 없는데, 참고하면 좋을 것 같다.
원형 이중 연결리스트
일반 연결리스트는 다음과 같이 생겼을 것이다.
A -> B -> C -> null
그러나 원형 이중 연결리스트란, 다음과 같이 연결되어있다.
모든 노드가 원형으로 연결되어있으며, 좌우로도 연결되어 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n;
static int m;
static int k;
static int[][] winterFood;
static int[][] soil;
static Tree[][] trees;
static int[] dx = {0, 0, -1, 1, 1, 1, -1, -1};
static int[] dy = {-1, 1, 0, 0, 1, -1, 1, -1};
static StringBuilder sb = new StringBuilder();
static class Tree {
int cnt = 0;
int age = 0;
Tree before;
Tree next;
public Tree() { // 헤더 트리 만들기
before = next = this;
}
public Tree(int age) { // 문제에서 주어지는 트리 만들기
this.age = age;
cnt = 1;
}
public Tree(int age, int cnt) { // 번식할 트리 만들기(개수도 필요함)
this.age = age;
this.cnt = cnt;
}
// 문제에서 입력으로 주어지는 나무의 위치는 모두 다르다고 했다.
// 이후, 나무가 번식을 하면 새로운 나무를 추가해 주어야 하는데,
// 현재 Tree의 두번째 부분(첫번째는 편의상 빈 나무임 = 헤더)에 넣어주면 된다.
// A(헤더)의 뒤에 B를 넣으면 된다.
// A -> B -> C => A -> D -> B -> C
public void add(Tree tree) {
this.next.before = tree;
tree.next = this.next;
tree.before = this;
this.next = tree;
}
// X.delete(Y)
// X 트리부터 Y트리 전까지 연결됨.
// A -> D -> C -> B 가 있다고 할 때
// A.delete(B) : A -> D
// A.delete(C) : A -> D -> B
// D.delete(B) : D -> C
// X == Y라면 자기 자신만 남음.
// X < Y라면 그대로.
// add를 하면 나이 순서대로 정렬이 될텐데
// 양분을 못 먹는 나무 이후로부터는 전부 죽어버린다.
// A -> B -> C -> D 가 있을때, C부터는 양분을 못먹어서 죽어버린다고 할 때
// A.delete(C)를 해주면 A -> B만 남게 되는 것이다.
public void delete(Tree tree) {
tree = tree.before;
tree.next = this;
this.before = tree;
}
}
static void setInputs() throws Exception {
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());
winterFood = new int[n][n];
soil = new int[n][n];
trees = new Tree[n][n];
for (int r = 0; r < n; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < n; c++) {
winterFood[r][c] = Integer.parseInt(st.nextToken());
soil[r][c] = 5;
trees[r][c] = new Tree();
}
}
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());
trees[x][y].add(new Tree(z));
}
}
private static void performSpringAndSummerOperation() { // 봄 행동(여름을 곁들인)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
boolean canAbsorbSoil = true;
Tree treeToDelete = null;
Tree tree = trees[i][j].next;
while (tree.age > 0) { // 나무 끝까지 탐색해서 다시 헤더로 돌아 온다면 종료
// 양분 섭취
if (canAbsorbSoil) {
int sum = tree.cnt * tree.age; // 해당 나무가 양분을 얼마나 섭취할 수 있니?
if (soil[i][j] >= sum) { // 양분 섭취가 가능하다!
soil[i][j] -= sum;
tree.age++;
} else { // 양분 섭취를 못해요!
/**
* 여름
*/
treeToDelete = performSummerOperation(i, j, tree);
canAbsorbSoil = false; // 더이상 양분을 먹을 나무는 없고 전부다 토양으로 돌아가요! 슬픕니다.
}
} else { // 너흰 이제 토양으로 돌아가라.
soil[i][j] += tree.cnt * (tree.age / 2);
}
tree = tree.next; // 다음 트리를 탐색합니다.
}
// 모든 트리를 탐색했으니, 이제 제거할 트리가 있는지 찾아볼까요?
if (treeToDelete == null) {
continue;
} // 제거할 트리가 있다면?? 제거해주면 됩니다.
trees[i][j].delete(treeToDelete);
}
}
}
static Tree performSummerOperation(int i, int j, Tree tree) { // 여름 행동
Tree treeToDelete;
int ableTreesCount = soil[i][j] / tree.age; // 현재 토양에서 지금 나이의 나무 몇그루가 양분을 섭취할 수 있나?
soil[i][j] -= ableTreesCount * tree.age; // 양분을 먹었어요!
soil[i][j] +=
(tree.cnt - ableTreesCount) * (tree.age / 2); // 죽은 나무는 나이의 절반만큼 양분으로 돌아갑니다!
if (ableTreesCount > 0) { // 양분을 먹은 나무가 있었다면
tree.cnt = ableTreesCount; // tree의 cnt를 다시 갱신해준다.
tree.age++; // 한 살 더 먹으렴
treeToDelete = tree.next; // 이 다음 나무부터는 제거 해버린다.
} else { // 아무도 양분을 못먹었다면 이 나무부터 제거 해버린다.
treeToDelete = tree;
}
return treeToDelete;
}
private static void performAutumnOperation() { // 가을 행동
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Tree tree = trees[i][j].next;
while (tree.age > 0) { // 헤더로 다시 돌아오면 종료.
// 나이가 5의 배수인 나무의 경우
if (tree.age % 5 == 0) {
for (int dir = 0; dir < 8; dir++) { // 8방 탐색 슛~~
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) { // 맵 밖으로 벗어나면 continue
continue;
}
if (trees[nx][ny].next.age == 1) { // 이미 해당칸에 다른칸에서 번식해온 나무가 있으면
// 헤더만 존재했다면 해더의 age는 0이라 조건을 만족 못해요.
trees[nx][ny].next.cnt += tree.cnt; // 이제 번식할 나무의 개수만 더해주면 된다.
continue;
}
trees[nx][ny].add(
new Tree(1, tree.cnt)); // 해당 칸에 처음 번식을 하는거라면 나이는 1, 번식할 나무의 개수로 tree 생성
}
}
tree = tree.next; // 다음 트리 탐색
}
}
}
}
private static void performWinterOperation() { // 겨울 행동
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
soil[i][j] += winterFood[i][j];
}
}
}
static int calculateAnswer() { // 답 계산
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Tree tree = trees[i][j].next;
while (tree.age > 0) { // 헤더로 다시 돌아오면 종료
ans += tree.cnt; // 나무 count 해주기
tree = tree.next; // 다음 트리로 Go
}
}
}
return ans;
}
public static void main(String[] args) throws Exception {
setInputs();
for (int year = 1; year < k + 1; year++) { // 1년부터 K년 까지
performSpringAndSummerOperation();
performAutumnOperation();
performWinterOperation();
}
int ans = calculateAnswer();
sb.append(ans);
System.out.println(sb);
}
}