백준-16235) 나무 재테크

1. 문제 링크

백준-16235-G3) 나무 재테크 (https://www.acmicpc.net/problem/16235)

2. 문제 해석

-N*N사이즈의 땅에 M개의 나무를 심고 아래 작업을 K년간 반복한다.
이후 살아있는 나무의 수를 출력한다. ( 초기 땅의 양분은 전부 5이다. )
봄 : 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 양분이 부족하면 죽는다.
여름 : int(죽은 나무들의 나이/2)만큼 땅에 양분을 추가하고 죽은 나무가 사라진다.
가을 : 나이가 5의 배수인 나무가 있다면 인접 8개의 칸에 나무가 1인 나무를 추가한다.
겨울 : 모든 땅에 주어진 양($A[i][j]$)만큼 양분을 추가한다.

• 1) 입력

  • (1) 땅의 가로 세로 길이 N:int, 나무의 수 M:int, 년수 K:int에 대하여,
        1 ≤ N ≤ 10, 1 ≤ M ≤ N2, 1 ≤ K ≤ 1,000
  • (2) A배열의 정보가 N줄에 걸쳐 주어진다. (1 ≤ A[r][c] ≤ 100)
        "A[r][c] ×N"×N줄
  • (3) 나무의 정보(x좌표 x:int, y좌표 y:int, 나이: z)가 M줄에 걸쳐 주어진다.
        "x y z"×M줄
  
  

• 2) 출력

  • (1) 살아있는 나무의 수 living_trees_number:int
  
  

• 3) 풀이 전략

  • (1) 2중 리스트 fertilizer(양분 정보 저장)와, 3중 리스트 trees를 생성한다.
  • (2) 새로운 나무가 (x,y)에 있다면 trees[x][y]에 추가한다. 이 경우, 조건상 먼저 들어온 나무가 항상 나이가 많다.
  • (3) 봄과 여름을 동시에 진행하여, trees[x][y]의 뒤부터 체크한다. 죽는 나무가 생길 경우 0~죽은 나무의 index까지 전부 다 죽이고 양분으로 바꾼 뒤 다음 x,y를 체크한다.
  • (4) 가을과 겨울을 진행한다.
  • (5) 이를 K회 반복한 뒤 trees[x][y]의 len 합을 계산한다.

3. 코드

• 1) 작성 코드

  import sys
  
  def main():
      N, M, K = map(int, sys.stdin.readline().rstrip().split())
      fertilizer = [[5]*(N+1) for _ in range(N+1)]
      trees = [[[] for _ in range(N+1)] for _ in range(N+1)]
      A = []
      for _ in range(N):
          A.append(list(map(int, sys.stdin.readline().rstrip().split())))
      for _ in range(M):
          x, y, z = map(int, sys.stdin.readline().rstrip().split())
          trees[x][y].append(z)
      for _ in range(K):
          #봄 and 여름
          for i in range(1,N+1):
              for j in range(1,N+1):
                  for k in reversed(range(len(trees[i][j]))):
                      if trees[i][j][k] <= fertilizer[i][j]:
                          fertilizer[i][j] -= trees[i][j][k]
                          trees[i][j][k] += 1
                          continue
                      for dead_tree in trees[i][j][:k+1]:
                          fertilizer[i][j] += dead_tree//2
                      trees[i][j] = trees[i][j][k+1:]
                      break
          #가을
          for i in range(1,N+1):
              for j in range(1,N+1):
                  for tree in trees[i][j]:
                      if tree%5 == 0:
                          for dx, dy in [(1,1),(1,0),(1,-1),(0,-1),(0,1),(-1,-1),(-1,0),(-1,1)]:
                              if 0 < i+dx < N+1 and 0 < j+dy < N+1:
                                  trees[i+dx][j+dy].append(1)
          #겨울
          for i in range(1,N+1):
              for j in range(1,N+1):
                  fertilizer[i][j] += A[i-1][j-1]
  
      count = 0
      for i in range(1,N+1):
          for j in range(1,N+1):
              count += len(trees[i][j])
      print(count)
  
  main()

• 2) 코드 평가

  • (1) 시간복잡도