16235 - 나무 재테크

 

---

 

문제

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

16235번: 나무 재테크

 

풀이

삽질의 흔적

 

요구사항 같은 경우에는, 크게 설명할 게 없다.

각 칸마다 1개 이상의 나무들을 저장할 수 있는 리스트와, 양분을 저장할 수 있는 저장 공간을 만들어둔다.

 

이후 봄, 여름, 가을, 겨울 로직을 순서대로 실행한다.

 

봄에서 특정칸의 나무들을 모두 체크할 때, 만약 현재 양분으로 나무들을 못주면 죽는 나무로 처리한다.

그리고 양분을 줄 수 있는 나무중 5의 배수인 나무의 위치를 따로 저장해둔다.

 

이렇게 해두면 여름의 로직은 봄 로직을 돌리면서 한 번에 끝낼 수 있고,

이후에 가을의 로직도 1차원 배열에 저장된 좌표들 기준으로 8방향에 나무를 번식시켜주면 된다.

 

겨울은 완전 독립적으로 시행하면 된다.

 

 

대충 로직을 설명했으나, 이 문제는 시간복잡도가 가장 큰 관건이다.

그리고 핵심은 나무를 어떻게, 오름차순으로 저장할것이냐가 문제이다.

 

문제의 조건에는 이런게 있다.

• 입력으로 주어지는 나무의 위치는 모두 서로 다름
• 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.

위의 첫번째 조건을 생각해보면, 처음 입력받을때 같은 장소에 나무가 2개씩 심어지는 경우는 없다.

두번째 조건을 생각해보면, 번식할때는 무조건 나이가 1인 나무가 들어온다. (당연히 1은 무조건 최솟값이다.)

 

해당 조건들을 잘 따져본다면 덱을 사용하여 효율적으로 풀 수 있다.

 

입력 나무는 그냥 넣어주고, 이후로 추가되는 나무들은 무조건 번식이니 오름차순에 맞게 덱에 넣어주면 된다.(왼쪽에서 부터)

이후 특정 위치에서 나무들을 검사할때는 오름차순으로 검사해보고, 유효한 값(양분을 먹을 수 있다면)들은 오른쪽에서 넣어주면 된다. 작은값부터 검사하고, 점점 값이 커지니 오른쪽으로 넣어야 오름차순이 유지된다.

 

결국 덱을 사용하는게 핵심포인트이다.

 

 

추가로, 나는 처음에 2차원배열 대신 dictionary를 사용해서 양분과 나무리스트들을 저장하고 사용했다. 또한 set을 통하여 현재 나무들이 존재하는 위치를 저장해두고 돌면서 사용했는데.. 시간초과가 걸렸다.

이후에 dictionary를 2차원 리스트로만 바꾸고, 모두 순회하면서 나무가 있는지 없는지 검사하는 방식으로 수정했고 그러고 나서야 통과 판정을 받을 수 있었다.

 

dictionary에서 key - hash로 접근하거나, set으로 접근하는것 모두 O(1)로 알고 있었는데, 아무래도 이런 자료구조들은 넓게 퍼져있는 값에 접근할때 효율적으로 사용할 수 있는 거 같다. 이렇게 n의 크기가 크지 않고, 연속된 데이터에 접근하는 경우 2차원 리스트가 훨씬 빠른 거 같다. 이거 때문에도 시간 엄청 날렸다..

 

 

코드

from sys import stdin
from collections import deque

# Initialize
dx = [ 0, 0, 1, -1, 1,  1, -1, -1]
dy = [-1, 1, 0,  0, 1, -1,  1, -1]

n, m, year = map(int, stdin.readline().rstrip().split())
A = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
saved = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        saved[i][j] = [5, deque()]

for _ in range(m):
    x, y, age = map(int, stdin.readline().rstrip().split())
    saved[x][y][1].append(age)

# main logic
for _ in range(year):
    breed = []

    # 봄 여름
    for x in range(1, n+1):
        for y in range(1, n+1):
            if len(saved[x][y][1]) > 0:
            
                temp = deque()

                # 나무 리스트를 모두 돌아본다.
                feed = saved[x][y][0]
                trees = saved[x][y][1]
                death_feed = 0
                for i in range(len(trees)):
                    age = trees[i]
                    if feed >= age:
                        feed -= age
                        temp.append(age+1)
                        if (age + 1) % 5 == 0:
                            breed.append([x, y])
                    else:
                        # 만약 더 이상 못먹는 상황이라면 죽는 나무들이다.
                        death_feed += (trees[i]//2)

                    saved[x][y] = [feed + death_feed, temp]

    # 가을이 되면 5의 배수인 친구들을 번식시켜준다.
    for val in breed:
        x, y = val
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # 번식이 가능하다면 번식 시켜주고, 나무 존재 위치를 갱신한다.
            if 1 <= nx <= n and 1 <= ny <= n:
                saved[nx][ny][1].appendleft(1)
    # 겨울에는 양분 추가해준다.
    for i in range(n):
        for j in range(n):
            saved[i + 1][j + 1][0] += A[i][j]

answer = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        if len(saved[i][j][1]) != 0:
            answer += len(saved[i][j][1])

print(answer)

 

후기

 

이틀연속으로 시간복잡도에 엄청 치이는 문제를 풀었더니 어지럽긴하다.. 그래도 이건 하루를 넘기지 않고 풀어서 다행이라고 생각한다!!!.. 

 

각 자료구조들의 디테일하게 다른점을 안다면 더 수월하게 문제를 풀 수 있을 거 같다. dictionary 와 list의 접근에 있어서 그렇게 큰 시간차이가 날 줄 전혀 몰랐다.