[백준] 16235번. 나무 재테크(JAVA)

문제

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

---

풀이(27분)

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

public class Main {

    static int[][] A;
    static int[][] fertilizer;
    static int n, m, k;
    static ArrayList<Point>[][] map;
    static int[] dx = new int[]{-1,-1,-1,0,0,1,1,1};
    static int[] dy = new int[]{-1,0,1,-1,1,-1,0,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new ArrayList[n][n];
        A = new int[n][n];
        fertilizer = new int[n][n];

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                map[i][j] = new ArrayList<>();
                A[i][j] = Integer.parseInt(st.nextToken());
                fertilizer[i][j] = 5;
            }
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
            map[r][c].add(new Point(r, c, age));
        }

        for(int i = 0; i < k; i++){
            year();
        }

        int answer = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                answer += map[i][j].size();
            }
        }

        System.out.println(answer);
    }

	// 봄 : 자신의 나이만큼 양분을 먹고, 나이가 1 증가. 한 칸에 나무는 여러개 있을 수 있으며 어린 나무부터 양분을 먹는다. 못 먹으면 즉시 사망
    // 여름 : 죽은 나무가 양분으로 변함. / 2 한 값으로 소수점 아래는 버림
    // 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하고, 인접한 8칸에 나이가 1인 나무가 생긴다.
    // 겨울엔 양분을 추가한다.
    static void year(){
        List<Point> deathList = new ArrayList<>();
        List<Point> breedingList = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                Collections.sort(map[i][j]);
                for(Point p : map[i][j]){
                    if(p.age <= fertilizer[i][j]){
                        fertilizer[i][j] -= p.age; // 비료 먼저 빼기
                        p.age++; // 나이 추가
                        if((p.age % 5) == 0){
                            breedingList.add(p);
                        }
                        continue;
                    }
                    deathList.add(p);
                }
            }
        }

        for(Point p : deathList){
            fertilizer[p.r][p.c] += p.age / 2;
            map[p.r][p.c].remove(p);
        }

        for(Point p : breedingList){
            int nowR = p.r;
            int nowC = p.c;
            for(int i = 0; i < 8; i++){
                int nextR = nowR + dx[i];
                int nextC = nowC + dy[i];
                if(isBounds(nextR, nextC)){
                    map[nextR][nextC].add(new Point(nextR, nextC, 1));
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                fertilizer[i][j] += A[i][j];
            }
        }
    }
    static boolean isBounds(int r, int c){
        return r >= 0 && r < n && c >= 0 && c < n;
    }

    static class Point implements Comparable<Point>{

        int r, c, age;
        public Point(int r, int c, int age) {
            this.r = r;
            this.c = c;
            this.age = age;
        }

        @Override
        public int compareTo(Point o) {
            return this.age - o.age;
        }
    }

}

---

문제 풀이 전략

 

1 ≤ N ≤ 10 의 범위로 인해 전부 체크해 주며 진행하는 것이 큰 시간 복잡도를 요구한다고 생각하지 않아 모두 탐색하는 방식으로 진행했다.

 

1. 각 지점마다 나무에 대한 정보를 ArrayList로 담아둔다. 

2. 각 지점을 탐색하며 계절에 맞는 활동을 진행한다.

3. 활동을 진행할 때 중복되게 체크되지 않게 배열에 담아둔 뒤 진행한다.

 

쓰인 도구

방향 탐색

[도구정리] 사방탐색

 

ArrayList<>[][]은 매우 유용한 자료구조이다!!!!