[백준 16235번] 나무 제테크 (악의 원흉 defaultdict)

거의 모든 문제에 defaultdict를 사용하는 나

이유는 일단 너무 편하다
그리고 처음에 모든 case에 대해 다 메모리를 할당하는 것보다 메모리를 아끼는 느낌을 받을 수 있다.

근데 이전에 올린 백준 14425번에 이어서 이번에도 계속 시간초과가 발생한 원인이 defaultdict였다..

 

 

🌼 문제 링크

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

16235번: 나무 재테크

• 티어: 골드 III
• 분류: 구현, 자료구조, 시뮬레이션

문제 자체는 그냥 그대로 구현만 하면 되는 아주 쉬운 문제이다.
그러나..

 

 

❗ 코드 1-1. Defaultdict를 이용한 구현 (실패)

import sys; input = sys.stdin.readline
from collections import defaultdict, deque

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
trees = defaultdict(deque)
for _ in range(M):
    x, y, age = map(int, input().split())
    trees[(x-1, y-1)].append(age)

grid = [[5 for _ in range(N)] for _ in range(N)]

def spring():
    num_trees = 0
    tree_age5 = []
    dead_trees = []
    for i, j in trees:
        tmp_ages = deque([])
        while trees[(i, j)]:
            age = trees[(i, j)].popleft()
            if grid[i][j] < age:
                trees[(i, j)].append(age)
                dead_trees.append((i, j, sum([age // 2 for age in trees[(i, j)]])))
                break
            else:
                grid[i][j] -= age
                tmp_ages.append(age+1)
                num_trees += 1
                if (age + 1) % 5 == 0:
                    tree_age5.append((i, j))
        trees[(i, j)] = tmp_ages
    return dead_trees, tree_age5, num_trees

def summer(dead_trees):
    for i, j, sum_ages in dead_trees:
        grid[i][j] += sum_ages

adj = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def fall(tree_age5, num_trees):
    for i, j in tree_age5:
        for di, dj in adj:
            i_, j_ = i+di, j+dj
            if 0<=i_<N and 0<=j_<N:
                trees[(i_, j_)].appendleft(1)
                num_trees += 1
    return num_trees

def winter():
    for i in range(N):
        for j in range(N):
            grid[i][j] += A[i][j]

for year in range(K):
    dead_trees, tree_age5, num_trees = spring()
    summer(dead_trees)
    num_trees = fall(tree_age5, num_trees)
    winter()

print(num_trees)

 

 

💡 코드 1-2. defaultdict를 이용하지 않은 구현 (성공)

import sys; input = sys.stdin.readline
from collections import deque

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
trees = [[deque() for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x, y, age = map(int, input().split())
    trees[x-1][y-1].append(age)

grid = [[5 for _ in range(N)] for _ in range(N)]

def spring():
    num_trees = 0
    tree_age5 = []
    dead_trees = []
    for i in range(N):
        for j in range(N):
            tmp_ages = deque([])
            while trees[i][j]:
                age = trees[i][j].popleft()
                if grid[i][j] < age:
                    trees[i][j].append(age)
                    dead_trees.append((i, j, sum([age // 2 for age in trees[i][j]])))
                    break
                else:
                    grid[i][j] -= age
                    tmp_ages.append(age+1)
                    num_trees += 1
                    if (age + 1) % 5 == 0:
                        tree_age5.append((i, j))
            trees[i][j] = tmp_ages
    return dead_trees, tree_age5, num_trees

def summer(dead_trees):
    for i, j, sum_ages in dead_trees:
        grid[i][j] += sum_ages

adj = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
def fall(tree_age5, num_trees):
    for i, j in tree_age5:
        for di, dj in adj:
            i_, j_ = i+di, j+dj
            if 0<=i_<N and 0<=j_<N:
                trees[i_][j_].appendleft(1)
                num_trees += 1
    return num_trees

def winter():
    for i in range(N):
        for j in range(N):
            grid[i][j] += A[i][j]

for year in range(K):
    dead_trees, tree_age5, num_trees = spring()
    summer(dead_trees)
    num_trees = fall(tree_age5, num_trees)
    winter()

print(num_trees)

 

코드 1-1과 코드 1-2는 trees의 초기화 방법만 다를 뿐 나머지 로직은 모두 같다.

코드 1-1의 경우, trees를 defaultdict(deque)로 구현해서, spring()에서 trees의 key에 대해서만 검사한다.

코드 1-2의 경우, trees를 [[deque() for _ in range(N)] for _ in range(N)]로 구현해서, spring에서 NxN의 모든 point에 대해 검사한다.

검사하는 수는 코드 1-2가 더 많겠지만, 코드 1-2만 통과하고, 코드 1-1은 시간초과로 실패했다.
defaultdict의 실행시간이 꽤나 오래 걸린다는 사실..
앞으론 절대 쓰지 말아야지

 

---

 

추가로, spring-summer-fall-winter을 다 나눠서 구현하지 않아도 다음과 같이 한번에 구현해서 더 효율적으로 코드를 짤 수 있다.

 

💡 코드 2. spring-summer-fall-winter을 한번에 구현

import sys; input = sys.stdin.readline
from collections import defaultdict, deque

N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
trees = [[deque() for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x, y, age = map(int, input().split())
    trees[x-1][y-1].append(age)

grid = [[5 for _ in range(N)] for _ in range(N)]
adj = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

for year in range(K):
    #spring
    new_trees = [[deque() for _ in range(N)] for _ in range(N)]
    num_trees = 0
    for i in range(N):
        for j in range(N):
            while trees[i][j]:
                age = trees[i][j].popleft()
                if grid[i][j] < age:
                    trees[i][j].append(age)
                    #summer
                    for age in trees[i][j]:
                        grid[i][j] += age // 2
                    break
                else:
                    grid[i][j] -= age
                    new_trees[i][j].append(age+1)
                    num_trees += 1
                    #fall
                    if (age+1) % 5 == 0:
                        for di, dj in adj:
                            i_, j_ = i+di, j+dj
                            if 0<=i_<N and 0<=j_<N:
                                new_trees[i_][j_].appendleft(1)
                                num_trees += 1

            #winter
            grid[i][j] += A[i][j]

    trees = new_trees

print(num_trees)

🍊 결과

위: 코드 1-2 / 아래: 코드 2