[CT] 나무 타이쿤

1. 문제

• n * n 격자에 서로 다른 높이를 가진 리브로수 나무 키우기
  • 특수 영양제 : 나무 키우기 위해 필요
    • 1 * 1 땅에 있는 나무 높이를 + 1
    • 씨앗만 있으면 높이 1의 나무 생성
    • 초기 특수 영양제 : n * n 격자 최하단 4개의 칸
    • 이동 규칙에 따라 움직임 : 이동 방향 + 이동 칸 수
      • 이동방향 : 1~8번 ➡️ ↗ ⬆️ ↖ ⬅️ ↙ ⬇️ ↘
      • n번 열에서 오른쪽으로 이동 : 1번열로 이동
  • 1년 동안 다음 단계를 거쳐 성장
    1. 특수 영양제를 이동 규칙에 따라 이동
    2. 특수 영양제를 이동 시킨 후 해당 땅에 특수 영양제를 투입
       • 투입 후 땅에 있던 특수 영양제는 소멸
    3. 특수 영양제를 투입한 리브로수의 대각선으로 인접한 방향에 높이가 1 이상인 리브로수가 있는 만큼 높이가 더 성장
       • 대각선으로 인접한 방향이 격자를 벗어나는 경우에는 세지 않음
    4. 특수 영양제를 투입한 리브로수를 제외하고 높이가 2 이상인 리브로수는 높이 2를 베어서 잘라낸 리브로수로 특수 영양제를 사고, 해당 위치에 특수 영양제를 올려둡니다.
    

⇒ n x n 격자의 칸에 리브로수의 각자 다른 높이와 각 년도의 이동 규칙이 주어질 때, 해당 년수가 모두 지나고 난 뒤 남아있는 리브로수 높이들의 총 합?

2. 풀이

• 이동규칙에 따라 이동했을 때 행과 열이 격자 범위 밖을 나갔을 때
  • if idx < 0 ⇒ idx += n
  • if idx > n ⇒ idx %= n
• 시간 복잡도 줄이기
  • 매년 기존의 특수 영양제는 제거하고 특수 영양제가 이동하는 과정에서 위치 정보값을 저장하는 구조를 list보다 set으로 저장하여 중간에 생기는 중복 값을 제거하며 진행!!
    • 시간 복잡도 줄이기 전 코드 (list)

      n, m = map(int, input().split())
      
      trees = [ list(map(int, input().split())) for _ in range(n) ]
      moves = [ tuple(map(int, input().split())) for _ in range(m) ]
      
      #     → ↗  ↑  ↖  ← ↙ ↓ ↘
      dr = [0, -1, -1, -1, 0, 1, 1, 1]
      dc = [1, 1, 0, -1, -1, -1, 0, 1]
      
      sur_r = [-1, -1, 1, 1]
      sur_c = [-1, 1, -1, 1]
      
      def moved(x):
          if x < 0:
              x =  x + n
          elif x >= n:
              x = x % n
          return x
      
      nutri = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1] ]
      
      for move in moves:
          d_idx, leng = move[0]-1, move[1]
          
          for i in range(len(nutri)):
              nutri[i][0] = moved(nutri[i][0] + dr[d_idx] * leng)
              nutri[i][1] = moved(nutri[i][1] + dc[d_idx] * leng)
      
          for i in range(len(nutri)):
              trees[nutri[i][0]][nutri[i][1]] += 1
      
          for n_r, n_c in nutri:
              surround = 0
              for i in range(4):
                  r = n_r + sur_r[i]
                  c = n_c + sur_c[i]
                  if 0 <= r < n and 0 <= c < n and trees[r][c] >= 1:
                      surround += 1
              trees[n_r][n_c] += surround
      
          new_nutri = []
          for i in range(n):
              for j in range(n):
                  if [i,j] not in nutri and trees[i][j] >= 2:
                      trees[i][j] -= 2
                      new_nutri.append([i,j])
          
          nutri = new_nutri
          
      answer = 0
      for row in trees:
          answer += sum(row)
      
      print(answer)

      

3. 최종 코드

n, m = map(int, input().split())

trees = [ list(map(int, input().split())) for _ in range(n) ]
moves = [ tuple(map(int, input().split())) for _ in range(m) ]

#     → ↗  ↑  ↖  ← ↙ ↓ ↘
dr = [0, -1, -1, -1, 0, 1, 1, 1]
dc = [1, 1, 0, -1, -1, -1, 0, 1]

sur_r = [-1, -1, 1, 1]
sur_c = [-1, 1, -1, 1]

def moved(x):
    if x < 0:
        x =  x + n
    elif x >= n:
        x = x % n
    return x

nutri = [[n-1, 0], [n-1, 1], [n-2, 0], [n-2, 1] ]

for move in moves:
    d_idx, leng = move[0]-1, move[1]
    
    for i in range(len(nutri)):
        nutri[i][0] = moved(nutri[i][0] + dr[d_idx] * leng)
        nutri[i][1] = moved(nutri[i][1] + dc[d_idx] * leng)

    for i in range(len(nutri)):
        trees[nutri[i][0]][nutri[i][1]] += 1

    for n_r, n_c in nutri:
        surround = 0
        for i in range(4):
            r = n_r + sur_r[i]
            c = n_c + sur_c[i]
            if 0 <= r < n and 0 <= c < n and trees[r][c] >= 1:
                surround += 1
        trees[n_r][n_c] += surround

    new_nutri = []
    for i in range(n):
        for j in range(n):
            if [i,j] not in nutri and trees[i][j] >= 2:
                trees[i][j] -= 2
                new_nutri.append([i,j])
    
    nutri = new_nutri
    
answer = 0
for row in trees:
    answer += sum(row)

print(answer)