🥚문제

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

• 구현
• 시뮬레이션

---

🥚입력/출력

---

🍳코드

# 참고: https://pacific-ocean.tistory.com/376
import sys
input = sys.stdin.readline
from collections import deque

# 봄, 여름
def ss():
    for r in range(N):
        for c in range(N):
            len_ = len(trees[r][c])
            for i in range(len_):
                # 봄
                if ground[r][c] - trees[r][c][i] >= 0:
                    ground[r][c] -= trees[r][c][i]
                    trees[r][c][i] += 1
                else:
                    # 오름차순이므로, 양분이 부족해지는 i부터 끝까지 다 양분이 부족할 것!
                    # 여름
                    for _ in range(i, len_):
                        ground[r][c] += trees[r][c].pop()//2
                    break

# 가을, 겨울
def fw():
    for r in range(N):
        for c in range(N):
            len_ = len(trees[r][c])
            # 가을
            for i in range(len_):
                if trees[r][c][i] % 5 == 0:
                    for j in range(8):
                        nr = r + dr[j]
                        nc = c + dc[j]
                        if 0 <= nr < N and 0 <= nc < N:
                            # 오름차순을 유지하기 위해 앞쪽에 추가
                            trees[nr][nc].appendleft(1)
            # 겨울
            ground[r][c] += A[r][c]
            

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, z = map(int, input().split())
    trees[x-1][y-1].append(z)

ground = [[5]*N for _ in range(N)]

# 나무 번식 방향
dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]

for _ in range(K):
    ss()
    fw()

# trees에 남아있는 나무의 개수 출력
ans = 0
for r in range(N):
    for c in range(N):
        ans += len(trees[r][c])
print(ans)

---

🧂아이디어

BFS

참고: https://pacific-ocean.tistory.com/376

• 엄청나게 시간초과를 만났던 문제 ⏰
  

• 이전에 작성한 코드는 봄, 여름, 가을, 겨울을 모두 각각 구분해서 함수로 작성했고, deque자료구조를 사용하여 (x좌표, y좌표, 나이) 데이터를 넣어준 뒤 나무 데이터가 변경될 때마다 나이 오름차순으로 계속해서 정렬했다.
  이 부분에서 시간초과가 발생했던 것 같다!

• 상단에 적어둔 링크의 코드에서 많은 것을 배울 수 있었다.
  • 봄, 여름과 가을, 겨울을 한 번에 처리하는 방법
  • 계속해서 나무 데이터를 정렬하지 않아도 된다! ⭐️
    • "처음에 입력으로 주어지는 나무의 위치는 모두 다르다" 라는 제한 사항 ->
      따로 sort할 필요 없이, 가을에 새로 추가되는 나무는 appendleft함수를 통해 deuqe 자료구조의 앞쪽으로 넣어주면 나무 데이터를 나이 오름차순으로 유지할 수 있다
      또한, 여름에 거름이 되어 사라지는 나무는 pop() 함수를 사용한다!