[백준 16235번] 나무 재테크 :: 늦깎이 IT

[백준 16235번 나무재테크 URL]

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

[기본 로직]

1. 1년(봄~겨울)이 지난 후 추가되는 영양분을 저장하는 배열 A를 선언합니다.

2. 각 계절마다 참고(?)해야할 현재의 영양분을 저장하는 배열 map을 선언합니다.

3. 각 위치(row, col)마다 나무의 갯수를 저장하기 위해 List 배열을 선언합니다.

[구체적인 로직]

1. doSpringAndSummer() 메소드

이 메소드에서는 봄, 여름에 일어나는 일을 함께 처리합니다.

각 위치(row, col)마다 저장된 나무를 순회하기 전에 나무의 나이를 기반으로 오름차순으로 정렬한 뒤,

나무의 나이와 그 위치에 있는 영양분을 비교하여 나무의 나이를 +1 증가시킬것인지 죽일것인지 결정합니다.

여기서 기존에 list[row][col]에 저장된 값(나무)은 삭제하지 않고 메소드 내에서 alive라는 List를 선언해,

나이가 증가된 나무들을 따로 저장합니다. "봄"이 끝나면 list[row][col]가 기존의 List가 아닌 새로 만들어진 

alive(나이가 증가된 나무들)을 참고하게 합니다.

만약 나무를 죽여야 하는 상황이라면, list에서 삭제하지 않고, 단순히 sum이라는 변수에 값을 저장합니다.

한 칸에 대한 "봄"의 로직을 모두 끝냈다면 sum에 저장된 값(죽은 나무가 변환된 영양분)을

map[row][col]에 더해주는 것이 "여름"에 대한 로직입니다.

2. doFall() 메소드

나무의 나이가 5의 배수이면 인접한 8방향으로 나이가 1인 나무를 추가합니다.

3. doWinter() 메소드

map[][]에 초기 영양분인 A[][]를 더해줍니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M, K;
    static int[][] map;
    static int[][] A;
 
    static List<Integer>[][] list;
 
    static int[] dirX = new int[] { 0, 0, 1, -1, -1, -1, 1, 1 };
    static int[] dirY = new int[] { 1, -1, 0, 0, -1, 1, -1, 1 };
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    static Comparator<Integer> comparator = new Comparator<Integer>() {
 
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    };
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
        A = new int[N][N];
        list = new ArrayList[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
                list[i][j] = new ArrayList<>();
                map[i][j] = 5;
            }
        }
 
        for (int i = 0; i < M; i++) {
 
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
            list[row][col].add(age);
        }
        for (int i = 0; i < K; i++) {
            doSpringandSummer();
            doFall();
            doWinter();
        }
 
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ans += list[i][j].size();
            }
        }
        System.out.println(ans);
    }
 
    public static void doSpringandSummer() {
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < N; j++) {
 
                int sum = 0;
                Collections.sort(list[i][j], comparator);
                List<Integer> alive = new ArrayList<>();
 
                for (int k = 0; k < list[i][j].size(); k++) {
 
                    int tree = list[i][j].get(k);
 
                    if (map[i][j] - tree >= 0) {
                        map[i][j] -= tree;
                        alive.add(tree + 1);
                    } else {
                        sum += (tree / 2);
                    }
                }
                list[i][j] = alive;
                map[i][j] += sum;
            }
        }
    }
 
    public static void doFall() {
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < N; j++) {
 
                for (int k = 0; k < list[i][j].size(); k++) {
 
                    int tree = list[i][j].get(k);
 
                    if (tree % 5 == 0) {
 
                        for (int dir = 0; dir < 8; dir++) {
 
                            int row = i + dirX[dir];
                            int col = j + dirY[dir];
                            if (isBoundary(row, col)) {
                                list[row][col].add(1);
                            }
                        }
                    }
                }
            }
        }
    }
 
    public static void doWinter() {
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < N; j++) {
                map[i][j] += A[i][j];
            }
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
}