BOJ16235_나무 재테크(시간제한 변경으로 다시)

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

문제정리

1. 각각의 칸은 (r,c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수 , c는 가장 왼쪽으로부터

떨어진 칸의 개수이다. r과 c는 1부터 시작한다.

2. M개의 나무를 구매해 땅에 심었다.

3. 사계절

(1) 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가

있는 1*1크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면,

나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을

먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

(2) 여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로

나눈 값이 나무가 있던 칸에 양분으로 추가된다.

(3) 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의

칸에 나이가 1인 나무가 생긴다.

(4) 겨울에는 땅에 양분을 추가한다. 각 칸에 추가되는 양분은 입력으로 주어진다.

4. K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.

문제issue

1. list를 사용해서 sort를 해주는 시간을 어떤식으로 줄여야 하나?

- 덱을 사용해서 새로 생기는 나무들은 앞에 넣어준다.

2. 죽은 나무의 나이의 합으로 갱신하는게 아니고 각각의 나이 / 2를 양분으로 갱신해야 된다.

해결흐름

1. map[N][N]에는 각각의 칸에 남은 양분 nour

2. Deque에는 나무가 있는 위치 x,y , 나무의 나이 age

3. 봄

Deque를 하나씩 꺼내서 age와 map의 nour을 비교하여 나무의 나이를 증가시켜줄지 , dead_q에

add할지를 정한다.

4. 여름

dead_q에서 하나씩 꺼내서 map[x][y].nour += age / 2 해준다.

5. 가을

Deque를 하나씩 꺼내서 나무의 나이가 5의 배수이면 인접한 8개의 칸에 나이가 1인 나무를 추가

해준다. 다른 que에 add해주고 마지막에 Deque에 addFirst해준다.

6. 겨울

A배열을 map의 nour에 더해준다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static class tree {
        int x;
        int y;
        int z;
 
        public tree(int x, int y, int z) {
            super();
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
 
    private static int N;
    private static int M;
    private static int K;
    private static int[][] A;
    private static LinkedList<tree> dq;
    private static int[][] map;
    private static LinkedList<tree> q;
    private static LinkedList<tree> dead_q;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        A = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j <= N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dq = new LinkedList<tree>();
        q = new LinkedList<tree>();
        dead_q = new LinkedList<tree>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            dq.add(new tree(x, y, z));
        }
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] = 5;
            }
        }
        for (int k = 0; k < K; k++) {
            spring();
            summer();
            fall();
            winter();
        }
        System.out.println(dq.size());
    } // end of main
 
    private static void spring() {
        int dq_size = dq.size();
//        System.out.println("=========spring=========");
        for (int i = 0; i < dq_size; i++) {
            tree t = dq.poll();
            int x = t.x;
            int y = t.y;
            int age = t.z;
//            System.out.println("x : " + x + " y : " + y + " age : " + age);
            if (age <= map[x][y]) {
                map[x][y] -= age;
                dq.addLast(new tree(x, y, age + 1));
//                System.out.println("x : " + x + " y : " + y + "양분 : " + map[x][y]);
            } else if (age > map[x][y]) {
                dead_q.add(new tree(x, y, age));
//                System.out.println("x : " + x + " y : " + y);
            }
        }
 
    }
 
    private static void summer() {
        while(!dead_q.isEmpty()) {
            tree t = dead_q.poll();
            int x = t.x;
            int y = t.y;
            int age = t.z;
            map[x][y] += age / 2;
        }
//        System.out.println("=============summer================");
//        for (int i = 1; i <= N; i++) {
//            for (int j = 1; j <= N; j++) {
//                System.out.println("x : " + i + " y : " + j + "야웁ㄴ : " + map[i][j]);
//            }
//        }
    }
 
    private static int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
    private static int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
    private static void fall() {
        int dq_size = dq.size();
//        System.out.println("============fall==============");
        for (int i = 0; i < dq_size; i++) {
            tree t = dq.poll();
            int x = t.x;
            int y = t.y;
            int age = t.z;
//            System.out.println("x : " + x + " y : " + y + " age : " + age);
 
            if (age % 5 == 0) {
                for (int j = 0; j < dx.length; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
                        q.add(new tree(nx, ny, 1));
//                        System.out.println("nx : " + nx + " ny : " + ny);
                    }
                }
            }
            dq.addLast(new tree(x, y, age));
        }
//        System.out.println("1인 나무 생성");
        while (!q.isEmpty()) {
            tree t = q.poll();
//            System.out.println("x : " + t.x + " y : " + t.y + " z : " + t.z + " age : " + t.z);
            dq.addFirst(new tree(t.x, t.y, t.z));
        }
    }
 
    private static void winter() {
//        System.out.println("============winter============");
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] += A[i][j];
            }
        }
//        for (int i = 1; i <= N; i++) {
//            for (int j = 1; j <= N; j++) {
//                System.out.println("x : " + i + " y : " + j + "양분 : " + map[i][j]);
//            }
//        }
    }
} // end of class