[코드트리: 나무 박멸]

url: https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=1&pageSize=20
소요시간 : 3시간

import copy

# 설계 10분
# 격자크기 / 박멸 진행 년수/ 제초제 확산범위/ 제초제 남아잇는 년 수
n, m, k, c = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]


def print_arr():
    print("arr")
    for i in range(n):
        print(*arr[i])


def in_range(y, x):
    if 0 <= y < n and 0 <= x < n:
        return True
    return False


def main():
    global arr
    answer = 0
    remove_tree_arr = [[0 for _ in range(n)] for _ in range(n)]

    for time in range(1, m + 1):
        # 제초제 제거
        for i in range(n):
            for j in range(n):
                if remove_tree_arr[i][j] == 0: continue
                if time == remove_tree_arr[i][j] + c + 1:
                    remove_tree_arr[i][j] = 0
                    arr[i][j] = 0
        # 성장
        X = [-1, 0, 0, 1]
        Y = [0, 1, -1, 0]
        trees = []
        for i in range(n):
            for j in range(n):
                # 나무라면
                if arr[i][j] > 0:
                    trees.append((i, j))
        # 주변 체크 -> 개수이기에 copy할 필요 없음
        # 1. 성장
        copy_arr = copy.deepcopy(arr)
        for ty, tx in trees[:]:
            cnt = 0
            for _ in range(4):
                dy = ty + Y[_]
                dx = tx + X[_]
                if in_range(dy, dx) and arr[dy][dx] > 0:
                    cnt += 1
            copy_arr[ty][tx] += cnt
            cnt = 0
            spread_arr = []
            for _ in range(4):
                dy = ty + Y[_]
                dx = tx + X[_]
                # 빈칸에 번식 가능
                if in_range(dy, dx) and arr[dy][dx] == 0:
                    spread_arr.append([dy, dx])
                    trees.append((dy, dx))
                    cnt += 1
            if cnt != 0:
                spread = copy_arr[ty][tx] // cnt
                for sy, sx in spread_arr:
                    copy_arr[sy][sx] += spread
        arr = copy_arr
        print_arr()
        print()

        # 제초제
        dX = [-1, -1, 1, 1]
        dY = [-1, 1, -1, 1]

        max_ = -1
        max_idx = []

        for ty, tx in trees[:]:
            cnt = arr[ty][tx]
            remove_tree = []
            for _ in range(4):
                for i in range(1, k + 1):
                    dy = dY[_] * i + ty
                    dx = dX[_] * i + tx
                    if in_range(dy, dx):
                        # 빈칸이면
                        if arr[dy][dx] == 0 or arr [dy][dx] == -2:
                            remove_tree.append([dy, dx])
                            break
                        # 벽이면
                        if arr[dy][dx] == -1:
                            break
                        else:
                            cnt += arr[dy][dx]
                            remove_tree.append([dy,dx])
            if max_ < cnt:
                max_ = cnt
                max_idx = [[ty, tx, remove_tree]]
            elif max_ == cnt:
                max_idx.append([ty, tx, remove_tree])

        # 제초젤 뿌릴 나무 조차 없음 -> stop
        if len(max_idx) == 0: break
        if len(max_idx) > 1:
            max_idx.sort(key=lambda x: (x[1], x[0]))

        dgy, dgx, remove_tree = max_idx[0]
        answer += arr[dgy][dgx]
        remove_tree_arr[dgy][dgx] = time
        arr[dgy][dgx] = -2
        for rty, rtx in remove_tree:
            if arr[rty][rtx] != -2:
                answer += arr[rty][rtx]
            # 제초제 저장
            remove_tree_arr[rty][rtx] = time
            # 제초제 뿌림
            arr[rty][rtx] = -2
    print(answer)

main()

문제설명

1. 나무의 성장

• 인접한 네 칸 중 나무가 있는 칸의 수만큼 성장
• arr크기가 0 이상이어야 함

2. 나무의 번식

• 인접한 네 칸 중 벽(-1), 다른나무(>0), 제초제(-2) 모두 없는 칸에 번식 진행
• 그루 수 // 가능한 칸의 개수 만큼 번식
• 여기서 중요한 점이 번식이 완료한 나무에서 또 번식이 될 수 있으므로 꼭 배열을 복사한 상태에서 진행을 해야 한다.

3. 제초제를 뿌림(핵심포인트) -> c년동안 유지됨

• 나무 있는 칸에 뿌림 -> k칸만큼의 대각선 방향으로 전파가 됨
• 만약에 벽이거나(-1) 나무가 아예 없는 칸의 경우(제초제거나 빈칸!! 제초제가 이미 뿌려진 칸이라는 것이 중요) 해당 칸까지는 뿌려지지만 더 퍼지지 않음.
• 만약 제초제가 뿌려진 칸에 또 뿌려짐 -> 년도가 갱신됨
• 가장 많은 나무가 박멸되는 칸에 뿌림 -> 만약 여러개면 행이 작은 순서, 열이 작은 순서로 뿌리게 됨

핵심 포인트

1. 제초제를 뿌릴 때 나무가 아예 없는 칸이 제초제를 뿌린 칸도 포함이 되었음.
   또한 벽과 나무가 아예 없는 칸까지 제초제를 꼭 뿌려줘야 함.
   나의 경우 가장 많은 나무가 박멸될 곳을 구한 뒤에 리스트로 박멸할 곳을 넘겨준 뒤 나중에 제초제를 뿌려주는 작업을 진행했는데, 꼭 해당 리스트에 넣어줬어야 함.
   또한 제초제를 뿌려 죽는 나무의 수를 구하는게 정답이므로 해당 제초제를 뿌리면서 answer을 갱신했는데 꼭 제초제가 이미 있던 곳의 값은 -2이므로 이 값은 건너뛰어야 함!!!
2. 행은.. 제발 y값이야. 열이 x값이고 어케 외우지 (y러십니까 행님?)
3. 제초제를 뿌릴 나무조차 없는 경우는 모두 박멸된거니까 m에 상관없이 멈춰주기

깨달은점

• 확실히 명기님이 말씀하신 것처럼 일자로 푸니까 디버깅 짱쉬움! 그리고 전역변수 헷깔릴 일도 없어서 어이없는 실수를 줄일 수 있었음(GOOD)
• 문제 세번읽고 푸는 건 좋은데 정리한걸 다시 안보는게 문제. 다시 깨끗이 정리하기