백준 16235번: 나무 재테크 (Python)

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

16235번: 나무 재테크

접근

따로 알고리즘은 필요 없었지만, 시간이 엄청 빡빡하여 시간 초과만 주구장창 받다가 겨우 풀 수 있었다.

첫번째 코드는 Python으로는 풀지 못하고 PyPy3으로 겨우 정답 처리 가능하였고, 두번째 코드로 Python 정답 처리 하였다.

기본적으로 각 위치를 돌면서 봄에 나무를 체크하여 죽을 나무들을 체크하고, 죽은 나무들은 여름에 토양으로 되돌려 보내주며, 가을에는 나이가 5의 배수인 나무들이 씨앗을 뿌리고, 겨울에는 로봇이 비료를 주는 과정을 코딩해주면 된다.
이때, 죽은 나무들이 비료가 되는 것과, 로봇이 비료를 주는 것은 봄 이후에 적용한다면 순서에 영향을 받지 않아 여름의 작용도 마지막 겨울 계산할 때 합산해서 계산해주었다.

첫번째 코드에서는 시간 단축을 위하여 나무를 저장하는 N * N 행렬 각 요소에 deque 를 이용하고 이 deque에 해당 위치 나무들의 나이를 저장해 주었다. 각 위치의 deque에 나무들을 오름차순으로 저장해두고, 새로운 나무는 맨 앞 위치에 추가해줌으로써 각 위치의 나무들을 나이 작은 순서대로 양분 흡수 계산을 할 수 있다. deque 함수를 이용함으로써, appendleft 등의 기능을 작은 시간복잡도를 이용하여 시간을 단축할 수 있었다.

두번째 코드에서는 나무를 저장하는 N * N 행렬 각 요소에 딕셔너리를 이용하여 {나이: 해당 나이의 나무 수} 의 형태로 저장해주었다. 이렇게 딕셔너리를 이용함으로써 각 위치에 있는 나무들의 개수를 모두 순환할 필요 없이 각 위치에 있는 나무들의 나이 수 만큼만 순환하면 문제 해결이 가능하여, 첫번째 코드 대비 시간을 더욱 단축할 수 있었고, Python의 빡빡한 시간 안에 문제 해결 가능하였다.

코드

첫번째 코드

import sys
from copy import deepcopy
from collections import deque

rc = [0, 1, 1, 1, 0, -1, -1, -1]
cc = [1, 1, 0, -1, -1, -1, 0, 1]
N, M, K = map(int, sys.stdin.readline().split())
soil = [[5] * N for _ in range(N)]
# 나무를 저장하는 tree의 각 위치에 deque를 이용하고, 해당 위치의 나무들의 나이를 오름차순으로 저장해준다.
tree = [[deque() for _ in range(N)] for __ in range(N)]
A = []
for _ in range(N):
    A.append(list(map(int, sys.stdin.readline().split())))
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    tree[x - 1][y - 1].append(z)

while K:
    # 1년에 주어야 하는 비료의 기본값을 A함수를 복제함으로써 초기화하고, 나무들을 순환하며 비료가 되는 나무들을 추가해준다.
    fertile = deepcopy(A)
    seed = []
    for r in range(N):
        for c in range(N):
            len_t = len(tree[r][c])
            for k in range(len_t):
                # (r, c) 땅 위치의 나무들을 나이 작은 순서대로 순차적으로 탐색한다.
                age = tree[r][c][k]
                if soil[r][c] >= age:
                    # 땅에 남은 양분이 나무의 나이보다 크다면, 땅에서 나이만큼 양분을 먹고 나이를 늘려준다.
                    soil[r][c] -= age
                    tree[r][c][k] += 1
                    if (age + 1) % 5 == 0:
                        # 늘려준 나이가 5의 배수라면 가을에 씨앗을 뿌릴 나무를 저장해준다.
                        seed.append((r, c))
                else:
                    # 땅에 양분이 없다면 남은 나무들을 모두 거름으로 만들어 fertile matrix에 추가해주고 break
                    for _ in range(k, len_t):
                        fertile[r][c] += tree[r][c].pop() // 2
                    break
    for (r, c) in seed:
        # 씨앗 뿌릴 나무들의 8방향을 탐색하여 나이가 1인 나무를 추가해준다.
        for i in range(8):
            nr, nc = r + rc[i], c + cc[i]
            if 0 <= nr < N and 0 <= nc < N:
                tree[nr][nc].appendleft(1)
    for r in range(N):
        for c in range(N):
            # 모든 위치를 탐색하여 비료 추가해준다.
            soil[r][c] += fertile[r][c]
    K -= 1
number = 0
for r in range(N):
    for c in range(N):
        number += len(tree[r][c])
print(number)

두번째 코드

import sys
from copy import deepcopy

rc = [0, 1, 1, 1, 0, -1, -1, -1]
cc = [1, 1, 0, -1, -1, -1, 0, 1]
N, M, K = map(int, sys.stdin.readline().split())
soil = [[5] * N for _ in range(N)]
# 나무를 저장하는 tree의 각 위치에 dictionary를 이용하고, 해당 dictionary에 {나이: 해당 나이의 나무 수} 의 형태로 저장해준다.
tree = [[{} for _ in range(N)] for __ in range(N)]
A = []
for _ in range(N):
    A.append(list(map(int, sys.stdin.readline().split())))
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    tree[x - 1][y - 1][z] = 1

while K:
    # 연간 주어야 하는 비료를 A를 복제함으로써 초기화해주고, 비료가 되는 나무들을 추가해준다.
    fertilizer = deepcopy(A)
    for r in range(N):
        for c in range(N):
            if tree[r][c]:
                tmp = {}
                fertile = 0
                for age in sorted(tree[r][c].keys()):
                    # 나이 적은 나무 순서대로 탐색하여 양분이 부족해질때까지 나무에 양분을 주고, 나머지는 비료로 추가한다.
                    if age * tree[r][c][age] <= soil[r][c]:
                        soil[r][c] -= age * tree[r][c][age]
                        tmp[age + 1] = tree[r][c][age]
                    else:
                        survive = soil[r][c] // age
                        if not survive:
                            fertile += (age // 2) * tree[r][c][age]
                            continue
                        soil[r][c] -= age * survive
                        tmp[age + 1] = survive
                        fertile += (age // 2) * (tree[r][c][age] - survive)
                tree[r][c] = tmp
                fertilizer[r][c] += fertile
    for r in range(N):
        for c in range(N):
            if tree[r][c]:
                num = 0
                for age in tree[r][c].keys():
                    # 나무의 나이가 5의 배수인 나무들의 수를 모두 더해주고,
                    if age % 5 == 0:
                        num += tree[r][c][age]
                if num:
                    # 해당 위치의 8방향에 구해진 나무 수만큼 나이가 1인 나무를 더해준다.
                    for i in range(8):
                        nr, nc = r + rc[i], c + cc[i]
                        if 0 <= nr < N and 0 <= nc < N:
                            if 1 not in tree[nr][nc].keys():
                                tree[nr][nc][1] = num
                            else:
                                tree[nr][nc][1] += num
            # 비료를 더해준다.
            soil[r][c] += fertilizer[r][c]
    K -= 1
number = 0
for r in range(N):
    for c in range(N):
        number += sum(tree[r][c].values())
print(number)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!