백준 나무 재테크 [16325] 파이썬(Python) 코드 + 해설

백준 16325 나무 재테크 문제

문제 설명

상도는 N×N크기의 땅을 구매했다. 각 칸에는 나무를 심을 수 있으며, 처음에는 모든 칸에 양분이 5만큼 들어있다. 상도는 M개의 나무를 구매하여 땅에 심었다. 이 나무들은 매년 다음과 같은 과정을 거친다:

1. 봄: 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 한 칸에 여러 나무가 있으면 나이가 어린 나무부터 양분을 먹는다. 양분이 부족하면 나무는 즉시 죽는다.
2. 여름: 봄에 죽은 나무가 양분으로 변한다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 해당 칸에 양분으로 추가된다. 소수점 아래는 버린다.
3. 가을: 나이가 5의 배수인 나무가 번식한다. 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 땅을 벗어나는 칸에는 나무가 생기지 않는다.
4. 겨울: 각 칸에 양분이 추가된다. 추가되는 양분의 양은 입력으로 주어진다.

K년이 지난 후 살아남은 나무의 수를 구하는 것이 목표다.

입력 조건

• 첫째 줄: N (1≤N≤10), M (1≤M≤N^2), K (1≤K≤1000)
• 둘째 줄부터 N개의 줄: 겨울에 추가될 양분의 양을 나타내는 A 배열 (1≤A[r][c]≤100)
• 다음 M개의 줄: 나무의 위치 (x,yx, yx,y)와 나이 (z) (1≤x,y≤N, 1≤z≤10)

해결 방법

이 문제는 시뮬레이션 문제로, 각 년도마다 계절별로 나무와 땅의 상태를 업데이트해야 한다. N이 최대 10이므로 전체 땅의 크기는 최대 10×10이다. 하지만 K가 최대 1000이므로, 연산을 효율적으로 수행해야 한다.

나무의 나이를 관리할 때, 각 칸에 있는 나무들을 나이순으로 정렬하여 저장한다. 이를 위해 우선순위 큐나 리스트 정렬을 사용할 수 있지만, 매년 정렬하면 비효율적이다. 따라서 deque를 사용하여 나무를 나이순으로 관리하고, 필요한 경우에만 정렬한다.

16325 나무 재테크 파이썬(Python) 정답 코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력 받기
N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]  # 겨울에 추가될 양분
nutrition = [[5]*N for _ in range(N)]  # 초기 양분 상태
trees = [[deque() for _ in range(N)] for _ in range(N)]  # 각 칸의 나무들 (deque 사용)

# 나무 심기
for _ in range(M):
    x, y, z = map(int, input().split())
    trees[x-1][y-1].append(z)

# 나무들을 나이순으로 정렬
for i in range(N):
    for j in range(N):
        if trees[i][j]:
            trees[i][j] = deque(sorted(trees[i][j]))

# 8방향 이동을 위한 dx, dy 설정
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

# K년 동안 시뮬레이션
for _ in range(K):
    # 봄과 여름
    dead_trees = [[0]*N for _ in range(N)]  # 죽은 나무로부터 생성된 양분
    for i in range(N):
        for j in range(N):
            if trees[i][j]:
                alive = deque()
                while trees[i][j]:
                    age = trees[i][j].popleft()
                    if nutrition[i][j] >= age:
                        nutrition[i][j] -= age
                        alive.append(age+1)
                    else:
                        dead_trees[i][j] += age // 2
                trees[i][j] = alive
    # 여름
    for i in range(N):
        for j in range(N):
            nutrition[i][j] += dead_trees[i][j]
    # 가을
    for i in range(N):
        for j in range(N):
            if trees[i][j]:
                for age in trees[i][j]:
                    if age % 5 == 0:
                        for d in range(8):
                            nx = i + dx[d]
                            ny = j + dy[d]
                            if 0 <= nx < N and 0 <= ny < N:
                                trees[nx][ny].appendleft(1)
    # 겨울
    for i in range(N):
        for j in range(N):
            nutrition[i][j] += A[i][j]

# 살아있는 나무 개수 세기
result = 0
for i in range(N):
    for j in range(N):
        result += len(trees[i][j])
print(result)

코드 설명

1. 입력 및 초기화

• 입력: sys.stdin.readline()을 사용하여 입력 속도를 높인다.
• 나무 정보 저장: 각 칸에 심겨진 나무들의 나이를 deque로 저장한다.
• 초기 정렬: 나무들을 나이순으로 정렬하여 deque에 저장한다.

2. 시뮬레이션 진행

• 봄과 여름:
  • 나무들은 자신의 나이만큼 양분을 먹고 나이가 1 증가한다.
  • 양분이 부족한 나무는 죽어서 양분으로 변한다.
  • 나무들은 나이순으로 처리되며, 이를 위해 deque를 사용한다.
• 가을:
  • 나이가 5의 배수인 나무들은 번식하여 인접한 8칸에 나이가 1인 나무를 심는다.
  • 새로운 나무는 deque의 앞쪽에 추가하여 다음 봄에 먼저 양분을 먹을 수 있게 한다.
• 겨울:
  • 각 칸에 양분을 추가한다.

3. 결과 출력

• 모든 년도가 지난 후, 각 칸에 존재하는 나무의 수를 합산하여 출력한다.

주요 포인트

• 자료 구조 선택: 나무를 나이순으로 관리하기 위해 deque를 사용한다.
• 시간 복잡도 최적화: 매년 나무를 정렬하지 않고, 새로운 나무를 deque의 적절한 위치에 추가하여 정렬된 상태를 유지한다.
• 효율적인 반복문: 나무가 있는 칸만 순회하여 불필요한 연산을 줄인다.

주의 사항

• Python3가 아닌 시간초과를 피하기 위해 PyPy3로 진행해야 합니다.

16325 파이썬 정답 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.