나무박멸

분명히 골드 4문제였는데... 엉켜버린 이후에 다시 푸는게 엄청난 난제였음..

개인적으로 꼬리잡기놀이 보다 푸는 시간이 오래걸림

import sys, copy
from collections import deque
n, m, k, c = map(int, sys.stdin.readline().strip().split())
graph = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
t_dx = [0,0,1,-1] 
t_dy = [1,-1,0,0]
trees = []
jecho = [[0 for _ in range(len(graph[0]))] for _ in range(len(graph))]
j_dx = [1,-1,1,-1]
j_dy = [1,-1,-1,1]
answer = 0


def count_remove_trees(y, x):
    global j_dx, j_dy, graph, trees, n, k
    visit = [(y,x)]
    count = graph[y][x]
    for d in range(4):
        q = deque([])
        tmp_y = copy.deepcopy(y)
        tmp_x = copy.deepcopy(x)
        q.append((tmp_y,tmp_x))
        tmp_k = copy.deepcopy(k)
        while q:
            if tmp_k == 0:
                break
            tmp_y, tmp_x = q.popleft()
            nx = tmp_x + j_dx[d]
            ny = tmp_y + j_dy[d]
            if ny >= n or ny < 0 or nx >= n or nx < 0:
                break
            if graph[ny][nx] == -1:
                break
            if graph[ny][nx] == 0:
                visit.append((ny, nx))
                break
            if jecho[ny][nx] != 0:
                break
  
            visit.append((ny, nx))
            q.append((ny, nx))
            count += graph[ny][nx]
            tmp_k -= 1
    return count, visit

def print_graph(text):
    global graph
    print(text)
    for i in graph:
        print(i)
    print()

def jecho_tree():
    global trees
    max_tree = 0
    visit = []
    jy, jx = 0, 0
    for y, x in trees:
        jecho_count = count_remove_trees(y, x)
        if max_tree < jecho_count[0]:
                max_tree = jecho_count[0]
                visit = jecho_count[1]
                jy = y
                jx = x
        elif max_tree == jecho_count[0]:
            if jy > y:
                max_tree = jecho_count[0]
                visit = jecho_count[1]
                jy = y
                jx = x
            elif jy == y:
                if jx > x:
                    max_tree = jecho_count[0]
                    visit = jecho_count[1]
                    jy = y
                    jx = x
    return jy, jx, max_tree, visit

def decrease_jecho():
    global jecho
    for y in range(len(jecho)):
        for x in range(len(jecho[y])):
            if jecho[y][x] > 0:
                jecho[y][x] -= 1

def check_near_tree(y, x):
    global graph, t_dx, t_dy, n
    count = 0
    for d in range(4):
        nx = x + t_dx[d]
        ny = y + t_dy[d]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue
        if graph[ny][nx] == 0 or graph[ny][nx] == -1:
            continue
        count += 1
    return count

def check_near_location(y, x):
    global jecho, graph,  t_dx, t_dy, n, trees
    
    count = 0
    extendtrees = []
    for d in range(4):
        nx = x + t_dx[d]
        ny = y + t_dy[d]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue
        if graph[ny][nx] == 0 and jecho[ny][nx] == 0:
            count += 1
            extendtrees.append((ny, nx))
    if count != 0: 
        return graph[y][x] // count, extendtrees
    return -1, extend_tree
def grow_tree():
    global graph, trees
    tmp_graph = [[0 for _ in range(len(graph[0]))] for _ in range(len(graph))]
    for y, x in trees:
        tmp_graph[y][x] += check_near_tree(y, x)

    for y in range(len(graph)):
        for x in range(len(graph[y])):
            graph[y][x] += tmp_graph[y][x]
    return

def extend_tree():
    global graph, trees
    tmp_trees = []
    tmp_graph = [[0 for _ in range(len(graph[0]))] for _ in range(len(graph))]
    for y, x in trees:
        count, extendtrees = check_near_location(y, x)
        if count != -1:
            for ty, tx in extendtrees:
                if (ty, tx) not in tmp_trees:
                    tmp_trees.append((ty, tx))
                tmp_graph[ty][tx] += count

    for y in range(len(graph)):
        for x in range(len(graph[y])):
            graph[y][x] += tmp_graph[y][x]
    for tree in tmp_trees:
        trees.append(tree)

for y in range(len(graph)):
    for x in range(len(graph[y])):
        if graph[y][x] != 0 and graph[y][x] != -1:
            trees.append((y,x))
    

while m != 0:
  
    grow_tree()
    # print_graph("grow")

    extend_tree()
    # print_graph("extend")
    decrease_jecho()

    # print_graph("jecho")
    tmp_y, tmp_x, jecho_count, jecho_trees = jecho_tree()
    # print(tmp_y, tmp_x, jecho_count, "jecho_count")
    jecho[tmp_y][tmp_x] = c
    graph[tmp_y][tmp_x] = 0

    for y, x in jecho_trees:
        graph[y][x] = 0
        jecho[y][x] = c

    for y in range(len(graph)):
        for x in range(len(graph[y])):
            if graph[y][x] <= 0:
                if (y,x) in trees:
                    trees.remove((y,x))
    # print("jechomap")
    # for i in jecho:
    #     print(i)
    # print()

    
    answer += jecho_count
    m -= 1

print(answer)