[백준 16235번] 나무 재태크 - 파이썬

문제 링크:

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

16235번: 나무 재테크

---

풀이 유형:

구현, 시물레이션

 

★문제풀이 Point★

1. 나무의 정보를 3차원 리스트로 담기 (행, 열, 나이)

2. 문제를 꼼꼼히 읽으면서 사계절별로 구현

3. 사계절 중에 여름 양분 처리 중요

 

풀이 과정:

이 문제는 K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하는 전형적인 시물레이션 문제이다. 

구현, 시물레이션 문제는 문제를 꼼꼼히 읽어야 한다. 문장들이 다 코드에 녹아들기 때문이다.

 

1. 나무 정보를 받는 3차원 리스트(행, 열, 나무의 나이) tree에서 나무의 나이를 리스트가 아닌 deque으로 받는다. 

이는 가을에 나무가 번식을 하여 나이가 1인 나무를 생성할 때 맨 앞부분에 넣기 위함(appendleft 사용)이다.

 

2. 문제에서 제한 부분을 살펴보면 다음과 같이 제한이 걸려있다.

다음 문장이 이 문제에 핵심 포인트이다.

이 문장은 굳이 나무의 나이를 기준으로 정렬할 필요가 없음을 알려준다.

즉, deque을 리스트로 바꿔서 정렬(sort)하고, 리스트를 다시 deque으로 바꿔야 할 필요가 없다.

 

3. 봄, 여름, 가을, 겨울 순으로 구현을 해주면 되는데, 여기서 필자가 가장 어려웠던 점은 여름이다.

# 여름
# 양분이 부족하다면
else:
	# 뒤에 있는 모든 나무들이 양분이 부족하므로
	for _ in range(k, tree_cnt):
		# 전부 없애주고 양분으로 만들기
		food[i][j] += tree[i][j].pop() // 2
	break

각 위치에 있는 나무들이 오름차순으로 정렬 1)되어 있음으로, 양분이 부족할 때는 현재 나무부터 뒤에 있는 나무들을 전부 없애고 양분을 만들어주면 된다.

1) 오름차순 정렬 근거:

1. 위 2번에 해당하는 제한 문장으로 인해 처음 1년에는 입력값이 각 위치마다 나무가 최대 1개밖에 들어갈 수 없음.

2. 가을에 번식 후에는 나이가 1인 나무를 appendleft를 이용해 맨 앞으로 보내주므로 오름차순 정렬이 완성됨.

 

구현, 시물레이션 문제는 정말로 복잡한 문제이다. 하지만 이런 문제일수록 침착하게 풀어야 한다.

 

풀이 코드:

16235번 파이썬

다음 코드는 PyPy3로 실행해 풀었다.

 

# 16235번 나무 재태크

from collections import deque

# 봄과 여름을 같이 처리하는 함수
def spring_summer():
    # 각 위치마다 하나씩 살펴보며
    for i in range(n):
        for j in range(n):
            # 현재 위치에 있는 트리 개수 세기
            tree_cnt = len(tree[i][j])
            # 트리 개수만큼 반복하며
            for k in range(tree_cnt):
                # 봄
                # 현재 위치에 있는 양분이 나무 나이보다 많거나 같다면
                if food[i][j] >= tree[i][j][k]:
                    # 양분 공급
                    food[i][j] -= tree[i][j][k]
                    # 나무 나이 1 증가
                    tree[i][j][k] += 1
                # 여름
                # 양분이 부족하다면
                else:
                    # 뒤에 있는 모든 나무들이 양분이 부족하므로
                    for _ in range(k, tree_cnt):
                        # 전부 없애주고 양분으로 만들기
                        food[i][j] += tree[i][j].pop() // 2
                    break
    return

# 가을과 겨울을 처리하는 함수
def fall_winter():
    for i in range(n):
        for j in range(n):
            # 가을
            # 현재 위치에 있는 나무의 나이를 차례대로 받아
            for k in range(len(tree[i][j])):
                # 나무의 나이가 5의 배수라면
                if tree[i][j][k] % 5 == 0:
                    # 8가지 번식 이동방향을 확인
                    for l in range(8):
                        nx = i + dx[l]
                        ny = j + dy[l]
                        # 주어진 맵 안에서 번식이 가능하다면
                        if 0 <= nx < n and 0 <= ny < n:
                            # 나이가 1인 나무를 이동 위치에 우선적으로 추가
                            tree[nx][ny].appendleft(1)
            # 겨울
            # 양분 공급
            food[i][j] += s2d2[i][j]
    return


# 입력값 받기
n, m, k = map(int, input().split())
# 나무 정보를 받는 3차원 리스트 (행, 열, 나무의 나이)
tree = [[deque() for _ in range(n)] for _ in range(n)]
# 각 위치에 있는 양분 리스트
food = [[5] * n for _ in range(n)]
# 가을에 나무가 번식하는 8가지 방법
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 로봇 s2d2가 겨울에 추가하는 양분 리스트 입력받기
s2d2 = [list(map(int, input().split())) for _ in range(n)]
# 나무 정보 입력받기
for _ in range(m):
    x, y, z = map(int, input().split())
    # 나무 위치에 나무의 나이 정보 추가
    tree[x-1][y-1].append(z)

# K년이 될 때까지 나무 재태크 실시
for _ in range(k):
    spring_summer()
    fall_winter()

# 나무의 개수 세기
answer = 0
for i in range(n):
    for j in range(n):
        answer += len(tree[i][j])

# 정답 출력
print(answer)

 

 

16235 나무 재태크 파이썬