[BOJ] 백준 16235 나무 재테크 - Python/Java

문제

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

16235번: 나무 재테크

 

해설

이 문제에서 구현해야 하는 내용은 그렇게 어렵지 않습니다. 봄, 여름, 가을, 계절에 해야하는 일들을 그대로 코드로 구현하면 되는데요. 

 

우선 땅이 가진 양분 정보, 나무들의 정보, 추가되는 양분의 정보를 각각 저장하는 자료구조가 필요합니다. 저같은 경우 파이썬에서는 모두 리스트로 입력을 받았고, 자바에서는 나무들의 정보는 우선순위큐를 이용했고 나머지는 배열을 이용해서 받았습니다. 이 부분은 푸는 사람마다 다를 것 같습니다.

 

그리고 문제에서 말하는대로 그대로 따라서 구현만 해주면 문제는 해결되는데요.

 

봄에는 나무들의 나이와 땅의 양분 상태를 관찰하여 나무가 양분을 흡수할지, 죽은 나무가 될지를 결정하면 됩니다. 그리고 이 부분에서 이후에 '번식을 할 나무', '죽은 나무'를 각각 리스트에 담아서 저장해줍니다. 그리고 이 때 저장했던 리스트를 가지고 여름과 가을에 나무와 땅의 상태를 변화시켜주고, 겨울에는 맨 처음 인풋으로 주어진 양분을 땅의 양분 상태에 더해주면 됩니다.

 

다만, 이 문제에서 중요했던 부분은 "타이트한 시간 제한을 어떻게 해결할 것인가?"였습니다. 자바로 풀 때는 바로 제한 시간 내에 통과를 했지만 파이썬으로 했을 때는 제한 시간을 맞추기가 상당히 어려웠습니다. 파이썬으로 이 문제를 해결하기 위해서는 아래의 세세한 디테일을 통해 실행 시간을 최대한 단축시켜야 하는 것 같습니다.

 

1. 양분이 적은 나무를 우선으로 보기 위한 정렬을 할 때, "봄"이 시작할 때 한 번만 정렬을 수행해준다.

2. 죽은 나무나 번식을 할 나무를 볼 때 모든 지점을 탐색하는 대신, 봄에 미리 기록한 부분만 부분적으로 탐색한다.

 

풀이는 아래와 같습니다.

 

풀이 - 파이썬

import sys
input = sys.stdin.readline

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
n, m, k = map(int, input().split())

# 땅의 정보, 나무 정보, 양분 정보
graph = [[5] * (n+1) for _ in range(n+1)]
tree = [[[] for _ in range(n+1)] for _ in range(n+1)]
feed = [[0] * (n+1)] + [[0] + list(map(int, input().split())) for _ in range(n)]

for i in range(1, m+1):
    x, y, z = map(int, input().split())
    tree[x][y].append(z)

for _ in range(k):
    spread = []
    dead = []
    for i in range(1, n+1):
        for j in range(1, n+1):
            if tree[i][j]: # 나무가 존재하는 경우에 대해
                tree[i][j].sort() # 적은 양분을 가지고 있는 나무 우선
                temp = []
                for age in tree[i][j]:
                    if age <= graph[i][j]:
                        graph[i][j] -= age
                        age += 1
                        temp.append(age)
                        if age % 5 == 0: # 번식할 나무 목록에 추가
                            spread.append((i,j))
                    else: # 죽은 나무에 추가
                        dead.append((i,j,age // 2))
                tree[i][j] = temp

    for i, j, age in dead: # 죽은 나무는 양분이 된다.
        graph[i][j] += age

    for i, j in spread: # 나무 주변으로 번식한다.
        for k in range(8):
            nx, ny = i + dx[k], j + dy[k]  
            if 1 <= nx <= n and 1 <= ny <= n:
                tree[nx][ny].append(1)

    for i in range(1, n+1): # 땅에 양분을 공급한다.
        for j in range(1, n+1):
            graph[i][j] += feed[i][j]

answer = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        answer += len(tree[i][j])
print(answer)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B_16235 {
    static int[] dx = {-1,-1,-1,0,0,1,1,1};
    static int[] dy = {-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 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] graph = new int[n+1][n+1];
        for(int i = 1; i <= n; i++) {
            Arrays.fill(graph[i], 5);
        }
        int[][] feed = new int[n+1][n+1];
        // 각 위치에 있는 나무는 양분이 적은 순서대로 정렬된 우선순위 큐로 저장
        PriorityQueue<Integer>[][] tree = new PriorityQueue[n+1][n+1];
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++){
                feed[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                tree[i][j] = new PriorityQueue<>();
            }
        }
        for(int i = 1; i <= m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            tree[x][y].add(z);
        }

        while(k-- > 0){
            List<Point> dead = new ArrayList<>(); // 죽은 나무들의 정보
            List<Point> spread = new ArrayList<>(); // 번식할 나무들의 정보
            // 봄
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    PriorityQueue<Integer> temp = new PriorityQueue<>();
                    while(!tree[i][j].isEmpty()){
                        int age = tree[i][j].poll();
                        if(age <= graph[i][j]){
                            graph[i][j] -= age;
                            temp.add(++age);
                            // 나이가 5의 배수인 나무는 가을에 번식할 예정
                            if(age % 5 == 0){
                                spread.add(new Point(i, j, age));
                            }
                        }else{
                            dead.add(new Point(i, j, age));
                        }
                    }
                    tree[i][j] = temp;
                }
            }

            for(Point p : dead){
                graph[p.x][p.y] += p.age / 2;
            }

            for(Point p : spread){
                int x = p.x; int y = p.y;
                for(int i = 0; i < 8; i++){
                    int nx = x + dx[i]; int ny = y + dy[i];
                    if(1 <= nx && nx <= n && 1 <= ny && ny <= n){
                        tree[nx][ny].add(1);
                    }
                }
            }

            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    graph[i][j] += feed[i][j];
                }
            }
        }
        int answer = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                answer += tree[i][j].size();
            }
        }
        System.out.println(answer);
    }

     static class Point{
        int x, y, age;
        public Point(int x, int y, int age){
            this.x = x;
            this.y = y;
            this.age = age;
        }
    }
}