BOJ 16235번: 나무 재테크

문제

문제 바로가기> BOJ 16235번: 나무 재테크

16235번: 나무 재테크

 

풀이

 

C++

나이가 어린 나무부터 양분을 먹기 위해서 priorityQueue가 아닌, deque에 앞에 새로 번식한 나무를 넣어주는 방식으로 문제를 풀었다. 초기 입력 위치는 모두 다르고, 나이는 1씩 증가하므로, 이렇게 하면 정렬할 필요가 없어져서 시간 초과를 방지할 수 있다!

 

#include<iostream>
#include<deque>
#define MAX 11
using namespace std;

int N, M, K;
deque<int> tree[MAX][MAX];
int A[MAX][MAX], nutrient[MAX][MAX];
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};

void input(){
    cin >> N >> M >> K;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++) {
            cin >> A[r][c];
            nutrient[r][c] = 5; // 가장 처음에 양분은 모든 칸에 5만큼 들어있음
        }
    }

    int r, c, age;
    for(int i=0; i<M; i++){ // 입력으로 주어지는 나무의 위치는 모두 서로 다름
        cin >> r >> c >> age;
        tree[r][c].push_back(age);
    }
}

void year(){

    // 봄 & 여름
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            int t; // 나무
            for(t=0; t<tree[r][c].size(); t++){
                if(tree[r][c][t] <= nutrient[r][c]) {
                    nutrient[r][c]-=tree[r][c][t]; // 자신의 나이만큼 양분을 먹고
                    tree[r][c][t]++; //  나이가 1 증가
                } else break;
            }
            for(int i=tree[r][c].size()-1; i>=t; i--){ // 양분을 먹지 못하고 즉시 죽은 나무
                nutrient[r][c]+=tree[r][c][i]/2; // 여름에 양분으로 변함
                tree[r][c].pop_back(); // 죽음
            }
        }
    }

    // 가을 - 나무 번식
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++){
            for(int t=0; t<tree[r][c].size(); t++){
                if(tree[r][c][t]%5 == 0){ // 나이가 5의 배수
                    for(int d=0; d<8; d++){ // 나무 번식
                        int nr = r+dr[d];
                        int nc = c+dc[d];
                        if(nr<1 || nr>N || nc<1 || nc>N) continue;
                        tree[nr][nc].push_front(1); // 나이가 1인 나무가 생김 
                    }
                }
            }
        }
    }

    // 겨울 - 양분 추가
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++) nutrient[r][c]+=A[r][c];
    }
}

void output(){ // K년이 지난 후 살아남은 나무의 수
    int ans = 0;
    for(int r=1; r<=N; r++){
        for(int c=1; c<=N; c++) ans+=tree[r][c].size();
    } cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    while(K--) year();
    output();
}

 

Java

java에서는 deque 2차원 배열을 선언하는 방법을 몰라서 ,, (있나,,?)

Queue와 LinkedList를 이용해서 문제를 해결했다.

이 때도 `tree.addAll(0, newTree)` 코드를 통해 새로 생긴 나무들을 모두 앞에 넣어 주었다.

 

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

public class Main {
	
	static class Tree {
		int r, c, age;

		public Tree(int r, int c, int age) {
			this.r = r;
			this.c = c;
			this.age = age;
		}
	}
	
	private static final int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
	private static final int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
	private static int N, M, K;
	
	private static int[][] A, nutrient;
	static Queue<Tree> dead;
	static LinkedList<Tree> tree = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        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());

        A = new int[N+1][N+1];
        nutrient = new int[N+1][N+1];
		
	    for(int r=1; r<=N; r++){
	    	st = new StringTokenizer(br.readLine());
	        for(int c=1; c<=N; c++) {
	            A[r][c] = Integer.parseInt(st.nextToken());
	            nutrient[r][c] = 5; // 가장 처음에 양분은 모든 칸에 5만큼 들어있음
	        }
	    }
		
	    for(int i=0; i<M; i++){ // 입력으로 주어지는 나무의 위치는 모두 서로 다름
	    	st = new StringTokenizer(br.readLine());
	    	tree.add(new Tree(
	    			Integer.parseInt(st.nextToken()), // r
	    			Integer.parseInt(st.nextToken()), // c
	    			Integer.parseInt(st.nextToken()) // age
	    			));
	    }
	    while(K-- > 0) year();
	    System.out.println(tree.size());
	}

	private static void year() {
	    
        // 봄
        dead = new LinkedList<>();
        Iterator<Tree> iterator = tree.iterator();
        while(iterator.hasNext()) {
            Tree t = iterator.next();
            int r = t.r;
            int c = t.c;
            int age = t.age;

            if(nutrient[r][c] < age) { // 양분을 먹지 못하고 즉시 죽는 나무 
                dead.offer(t); // 죽음
                iterator.remove();
            }
            else {
                nutrient[r][c]-=age; // 자신의 나이만큼 양분을 먹고
                t.age++; //  나이가 1 증가
            }
        }
		
        // 여름
        while (!dead.isEmpty()) {
            Tree t = dead.poll();
            nutrient[t.r][t.c] += t.age / 2;
        }

        // 가을 - 나무 번식	
        LinkedList<Tree> newTree = new LinkedList<>();
        for(Tree t : tree) {
            int r = t.r;
            int c = t.c;
            int age = t.age;
            if(age%5==0) {
                for(int d=0; d<8; d++){ // 나무 번식
                    int nr = r+dr[d];
                    int nc = c+dc[d];
                    if(nr<1 || nr>N || nc<1 || nc>N) continue;
                    newTree.add(new Tree(nr, nc, 1)); // 나이가 1인 나무가 생김 
                }
            }
        }
        tree.addAll(0, newTree);

        // 겨울 - 양분 추가
        for(int r=1; r<=N; r++){
            for(int c=1; c<=N; c++) nutrient[r][c]+=A[r][c];
        }	
    }
}