백준 #16235 - 나무 재테크 : 구현, 시간

사계절을 차례차례 구현하고, 시간이 오래 걸릴만한 요소들을 제거해주면 되는 문제였습니다.

이슈 1. 문제 해석 (r,c) 와 (x,y)

문제에서 "각각의 칸은 (r, c)로 나타내며" 와 "처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고," 에서 x y 해석이 헷갈렸는데 r = x, c = y 로 해석해야합니다.
r = y, c = x 로 해석하고 코딩해도 예제 케이스는 다 통과되기 때문에 주의하세요! 예제 3~8 까지가 K 만 1씩 증가시키는 테케이고 K=6 까지 제공됩니다. x,y 해석을 잘못하면 K=7 부터 답이 다르게 도출됩니다.

이슈 2. 시간 초과

저같은 경우는 예제 3의 K=1000 으로 증가했을 때 time 이 "0.022~0.024" 일때 시간 초과, "0.0202~0.0215" 정도 나오는 코드로 통과했습니다.

시간 단축을 위한 수정 : sort 삭제

"나이가 어린 나무 부터" 에서 배열.sort() 를 사용했는데, 가을에 나이가 1인 나무가 추가되는것을 제외하면 항상 배열의 순서가 유지되고 나이는 모든 나무가 같이 먹으니 오름차순이 항상 유지되게 됩니다. 가을에 추가되는 1살짜리 나무만 핸들링 해주어 sort 를 제거합니다. deque 를 활용해서 appendleft 로 앞쪽에 추가해줄수도 있고, 배열.insert(0,1) 로 가장 앞쪽에 1 을 추가해주는 방법도 있습니다. 둘 다 sort 보다는 훨씬 빠를 것입니다.
저는 deque 자체가 무겁기 때문에 연산이 느릴 수 있다는 얘기가 있어서 일단 배열 insert 를 시도해봤는데 통과 됐습니다.
또 python3 -> pypy 로 Implementation (구현체) 을 변경했습니다.

구현 방식

나무 정보는 dict 로, 비료 정보는 2차원 배열로 관리했습니다.
모든 정보를 2차원 배열 하나에 한꺼번에 넣을 수도 있지만 dict 로 쪼개는게 코드 가독성이나 작성에 더 좋을 것 같아서 dict 를 사용했습니다. 예상하기로는 N 크기가 커지면 dict 로 관리하는게 실행시간 더 많이 들것 같긴한데, K 가 커지는건 큰 차이가 없어서 괜찮았던것 같습니다.
dict 구조는 (r,c) : [ages] 입니다. 땅 좌표가 key, 그 땅에 있는 나무들의 나이를 배열로 val 에 넣었습니다.
봄과 여름의 경우 기존 [나무] 배열을 돌면서 [살아남은 나무], [죽은 나무] 배열을 2개를 새로 생성해서 [나무] 를 [살아남은 나무] 로 바꾸고, [죽은 나무] 로 비료를 더하는 방식으로 해결했습니다.

구현 코드

# import time

def solution(input) : 
    N, M, K = list(map(int,input().split())) # 땅 NxN, 나무구매 M개, K년 후 나무개수
    ground = [[5 for _ in range(N)] for _ in range(N)]
    A = []
    for _ in range(N) : # s2d2 의 겨울 양분 배열 A
        A.append(list(map(int, input().split())))

    tree_dict = {} # key 배열 위치, val [나이] // 배열 위치는 (row,col)
    for r in range(N) :
        for c in range(N) :
            rt = r+1
            ct = c+1
            tree_dict[(rt,ct)] = []

    for _ in range(M) :
        r,c,z = list(map(int, input().split()))
        tree_dict[(r,c)].append(z)
    AROUND = [
        (-1,-1),
        (-1,0),
        (-1,1),
        (0,-1),
        (0,1),
        (1,-1),
        (1,0),
        (1,1),
    ]

    def year(tree_dict, ground) :
        # spring
        for r,c in tree_dict :
            # tree_dict[(r,c)].sort() # 나이 어린 순 sort
            new_age = []
            dead_age = []
            for age in tree_dict[(r,c)] :
                if ground[r-1][c-1] >= age : # 나이 먹을 수 있으면
                    ground[r-1][c-1] -= age
                    new_age.append(age+1)
                else :
                    dead_age.append(age)
            tree_dict[(r,c)] = new_age # 나이 증가
            # summer
            for age in dead_age :
                ground[r-1][c-1] += age//2
        # autumn
        for r,c in tree_dict :
            for age in tree_dict[(r,c)] :
                if age % 5 == 0 : # 5의 배수인 경우
                    for g in AROUND : # 주변 8칸
                        nr, nc = r+g[0], c+g[1]
                        if nr >= 1 and nr <= N and nc >= 1 and nc <= N : # 땅 안에 있다면
                            tree_dict[(nr,nc)].insert(0,1) # 1살짜리 추가
        # winter
        n_ground = []
        for i in range(N) :
            row = []
            for j in range(N) :
                row.append(ground[i][j]+A[i][j])
            n_ground.append(row)

        return tree_dict, n_ground

    def tree_count() :
        cnt = 0
        for rc in tree_dict :
            cnt += len(tree_dict[rc])
        return cnt

    for _ in range(K) :
        tree_dict, ground = year(tree_dict, ground)
    print(tree_count())
    
# start = time.time()
solution(input)
# end = time.time()
# print(end-start)