[백준 16235] 나무 재테크

문제보기

파이썬으로 풀어본 첫 알고리즘 문제이다.

처음에 문제를 읽었을 때는, 그저 문제에서 하라는대로 코딩을 하면 풀 수 있겠다 생각했지만 그건 아니었다.

가장 큰 실수를 범할 수 있는 부분 2가지가 있다.

첫째로, 봄에 양분이 모자라서 죽은 나무를 처리하기 위해 각 칸을 순회하면서 그 칸에서 죽은 나무를 삭제하는 동시에 바로 양분을 추가하는 것(여름 단계)이다.

즉, 각 칸을 순회할 때, 봄 단계의 처리가 모두 끝난 후에 여름 단계를 처리해야한다.

왜냐하면 각 칸을 순회할 때, 죽은 각 나무들의 양분을 바로 더해버리면 같은 칸에 있는 다음 나무 양분에게 영항을 끼치기 때문에 올바른 값이 나올 수가 없다.

둘째로, 문제에 다음과 같은 설명이 있다.

"처음 두 개의 정수는 나무의 위치 (x, y)를 의미한다."라는 것을 보고, 입력을 c, r(열과 행)으로 받아야겠다고 생각했다.

하지만 x와 y는 그저 변수일 뿐, 우리가 생각하는 좌표계로 바꿔버리면 안된다.

문제의 서두에 각각의 칸은 (r, c)로 나타내며, r과 c는 행과 열의 의미를 가지고 있다고 했으므로, x는 r이되고 y는 c가 되는 셈이다.

위의 두 가지를 주의해서 풀었더니 했더니 AC를 받았다.

import sys
 
inputLine = sys.stdin.readline().split()
n, m, k = int(inputLine[0]), int(inputLine[1]), int(inputLine[2])
 
field = [[5 for r in range(n + 1)] for c in range(n + 1)]
trees = [[list() for r in range(n + 1)] for c in range(n + 1)]
A = [[0 for r in range(n + 1)] for c in range(n + 1)]
 
for r in range(1, n + 1):
    inputLine = sys.stdin.readline().split()
    for c in range(1, n + 1):
        A[r][c] = int(inputLine[c - 1])
        
for i in range(m):
    r, c, age = list(map(int, sys.stdin.readline().split()))
    trees[r][c].append(age)
    
dr = (-1, -1, 0, 1, 1, 1, 0, -1)
dc = (0, 1, 1, 1, 0, -1, -1, -1)
 
for year in range(k):
    dead_trees = list()
    # spring & summer
    for r in range(1, n + 1):
        for c in range(1, n + 1):
            temp = 0
            for i in range(len(trees[r][c]) - 1, -1, -1):
                if field[r][c] >= trees[r][c][i]:
                    field[r][c] -= trees[r][c][i]
                    trees[r][c][i] += 1
                else:
                    temp += trees[r][c][i] // 2
                    trees[r][c].pop(i)
            field[r][c] += temp
 
    # autumn
    for r in range(1, n + 1):
        for c in range(1, n + 1):
            for i, age in enumerate(trees[r][c]):
                if age % 5 == 0:
                    # for all directions
                    for direction in range(8):
                        new_r = r + dr[direction]
                        new_c = c + dc[direction]
                        if 1 <= new_r <= n and 1 <= new_c <= n:
                            trees[new_r][new_c].append(1)
            # winter
            field[r][c] += A[r][c]
 
count = 0
for r in range(1, n + 1):
    for c in range(1, n + 1):
        count += len(trees[r][c])
print(count)