[python] BOJ 백준 16235: 나무재테크

1. 문제  

 

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다.

상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다.

나무 재테크란 작은 묘목을 구매해 어느정도 키운 후 팔아서 수익을 얻는 재테크이다. 상도는 나무 재테크로 더 큰 돈을 벌기 위해 M개의 나무를 구매해 땅에 심었다. 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.

이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.

봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.

가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.

겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.

K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.

2. 입력   

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 N개의 줄에 A배열의 값이 주어진다. r번째 줄의 c번째 값은 A[r][c]이다.

다음 M개의 줄에는 상도가 심은 나무의 정보를 나타내는 세 정수 x, y, z가 주어진다. 처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고, 마지막 정수는 그 나무의 나이를 의미한다.

3. 출력   

첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 문제에서 제시된대로 봄, 여름, 가을, 겨울에 해당되는 내용을 그대로 함수로 구현해주면된다. 양분을 저장하는 board배열과 나무들을 저장하는 tree배열을 각각 만들어주었고, board의 i,j에 들어있는 나무들에 대한 정보는 tree의 i,j의 똑같은 위치에 저장되게끔 인덱스를 맞추어 주었다. 봄, 여름, 가을, 겨울의 함수실행을 k번 반복해주고, 남은 나무들의 개수를 카운트해주었다. 

1) spring 함수: n*n 배열을 돌면서 나무는 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 문제에서 나이가 어린나무부터 양분을 먹는다고 하였으므로, 정렬을 해주어야한다. 만약 양분을 못먹으면 그 이후의 나무들은 모두 죽게되는데, 이때 del이나 remove와 같은 함수를 쓰면 for문에서 오류가 날수 있으므로 파이썬의 인덱싱 기능을 이용해주는 것이 좋다. 또한 죽은 나무들 배열에 대해서는 리턴을 해주어야 summar 함수에서 사용할 수 있다. 

2) summar 함수: spring함수에서 받은 죽은 나무들 배열을 돌면서 죽은 나무들의 나이의 나누기 2의 몫만큼을 양분으로 더해준다. 나머지는 버린다고 하였으므로 // 연산자를 쓰면된다.

3) fall 함수: n*n배열을 돌면서 나이가 5의 배수인 나무가 있다면 8가지 방향으로 나이가 1인 나무를 추가해준다. 이때 범위를 넘어가선 안되므로 범위체크를 해주어야한다.

4)  winter 함수: 문제에서 입력받은 양분만큼 추가해준다. 

5) 구현코드   

n,m,k=map(int,input().split()) 
a=[list(map(int,input().split())) for _ in range(n)] #추가되는 양분의 양 
board=[[5]*n for _ in range(n)] #양분정보 
tree=[[[] for i in range(n)] for j in range(n)] #나무정보 
death=[] #죽은나무배열 

#나무 번식하는 방향 
dx=[-1,-1,-1,0,0,1,1,1]
dy=[-1,0,1,-1,1,-1,0,1]

for _ in range(m):
  x,y,z=map(int,input().split())
  tree[x-1][y-1].append(z)

#봄
def spring():
  death=[] #죽은나무들 배열 
  for i in range(n):
    for j in range(n):
      tree[i][j].sort() #나이가 어린나무부터 
      for t in range(len(tree[i][j])):
        if board[i][j]>=tree[i][j][t]: #양분을 먹을수있으면 
          board[i][j]-=tree[i][j][t] #나이만큼양분먹기 
          tree[i][j][t]+=1 #나무나이 증가 
        else: #양분을 먹을수없으면 
          death.append((i,j,tree[i][j][t:])) #그 이후의 나무들 모두 죽음 
          tree[i][j]=tree[i][j][:t] #나무는 이전 인덱스 까지만 살아남음 
          break

  return death

#여름 
def summar(death):
  #죽은 나무들에 대해서 
  for i,j,t in death:
    for age in t: #양분더해주기 
      board[i][j]+=age//2

#가을 
def fall():
  for i in range(n):
    for j in range(n):
      for t in tree[i][j]:
        #나무나이가 5의배수이면 
        if t%5==0:
          for d in range(8): #8가지 방향으로 
            x,y=i+dx[d],j+dy[d] 
            if 0<=x<n and 0<=y<n: #범위를 넘어가지 않을때만
              tree[x][y].append(1)#번식 
#겨울 
def winter():
  for i in range(n):
    for j in range(n):#양분추가 
      board[i][j]+=a[i][j]
      
#k번만큼 반복 
for _ in range(k):
  death=spring()
  summar(death)
  fall()
  winter()

cnt=0 #살아남은 나무의 개수 
for i in range(n):
  for j in range(n):
    if tree[i][j]:
      cnt+=len(tree[i][j])

print(cnt)

 

⭐️난이도:  골드 4⭐️

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

16235번: 나무 재테크