[삼성기출] 나무박멸

출처 : https://www.codetree.ai/training-field/frequent-problems/tree-kill-all/description?page=3&pageSize=20&username=wondang99

사고과정

빡구현 문제이므로 차근차근 생각하면서 구현

def grow() :
    global count_world
    for i in range(n) :
        for j in range(n) :
            
            if world[i][j] <= 0 :
                if world[i][j]==-1 :
                    count_world[i][j] = -1
                continue

            for d in range(4) :
                n_x = i+d_x[d]
                n_y = j+d_y[d]
                if 0<=n_x<n and 0<=n_y<n and world[i][j]!=0 and world[i][j]!=-1:
                    if world[n_x][n_y]==0 :
                        # 이후 번식에서 쓸 count
                        if zecho[n_x][n_y]==0 : 
                            count_world[i][j]+=1
                    elif world[n_x][n_y]==-1 :
                        continue
                    else : #world[n_x][n_y]==1
                        world[i][j]+=1
            if count_world[i][j]==0:
                count_world[i][j]=-1

성장 파트
주변에 번식 가능하다면 count_world에 +1. 만약 다른 나무가 있다면 성장하므로 world에 +1. 그리고 이후 생성된 추가 조건으로 count_world=1

def plus() :
    global count_world
    for i in range(n) :
        for j in range(n) :
            if world[i][j]==0 or world[i][j]==-1 :
                continue
            for d in range(4) :
                n_x = i+d_x[d]
                n_y = j+d_y[d]
                # 비어있는 지대에 제초제도 없고 벽도 아니야. 나무의 유무는
                if 0<=n_x<n and 0<=n_y<n and count_world[n_x][n_y]==0 and count_world[i][j]!=0 and zecho[n_x][n_y]==0:
                    world[n_x][n_y] += world[i][j]//count_world[i][j]

번식 파트
지대도 비어 있고 제초제도 없고 벽도 아니면 번식 가능. world/count_world로 번식

def calJecho() :
    max_n, r_x, r_y = 0,0,0
    for i in range(n) :
        for j in range(n) :
            if world[i][j]==0 or world[i][j]==-1 :
                continue
            zecho=world[i][j]
            for d in range(4) :
                for cr in range(1,k+1) :
                    n_x = i+c_x[d]*cr
                    n_y = j+c_y[d]*cr
                    if 0<=n_x<n and 0<=n_y<n and world[n_x][n_y]!=-1 and world[n_x][n_y]!=0:
                        zecho+=world[n_x][n_y]
            if max_n<zecho:
                max_n = zecho
                r_x,r_y = i,j
    # print(r_x,r_y,max_n)
    if max_n ==0:
        return -1,-1
    return r_x, r_y

어디에 제초제를 뿌릴지 계산. 이후 생긴 추가 조건으로 만약 제초제를 뿌릴 데가 없다면 -1 반환

문제는 제초제 계산 파트 next가 벽이나 비어있다면 no action이 아니라 break을 해줘야 한다.

def jecho(r_x, r_y) :
    kill = world[r_x][r_y]
    for i in range(n) :
        for j in range(n) :
            if zecho[i][j]!=0 and world[i][j]==-1:
                zecho[i][j]-=1

    zecho[r_x][r_y]=c
    world[r_x][r_y]=0
    for d in range(4) :
        for cr in range(1,k+1) :
            n_x = r_x+c_x[d]*cr
            n_y = r_y+c_y[d]*cr
            if 0<=n_x<n and 0<=n_y<n:
                # if world[n_x][n_y]==-1:
                #     break
                if world[n_x][n_y]==-1 or world[n_x][n_y]==0 :
                    zecho[n_x][n_y]=c
                    break
                zecho[n_x][n_y]=c
                kill+=world[n_x][n_y]
                world[n_x][n_y]=0 # 동시에 못 만들게 해야 돼

제초제 살충 파트
제초제 뿌리고 나무 없애고 c를 통해 년수 유지

추가된 조건
1. count_world가 0이라도 기존에 나무가 존재할 수 있다. ( 주변이 막혀서 번식은 불가능하다면 count_world는 0임 ) 따라서 count_world==0이라는 조건으로 번식 유무를 결정할 수 없음. 위와 같은 경우가 존재할 수 있으므로 해당 조건에서 count_world를 -1로 대입 -> count_world!=0 이라면 나무 존재 조건 만족!

코드 구현부가 의미론적인 부분을 완전히 구현가능한가?

2. 처음 시작점이 나무가 아닌 벽인 상태에서 제초제 뿌릴 위치가 없다면 그대로 최초의 벽이 제초제 뿌릴 위치가 되버린다. 따라서 벽에 대해서는 제초제 계산을 고려하지 않아야한다.

+) index 위치 헷갈리지 마라, 한 개의 자료구조/함수는 한 개의 책임만 가지도록 역할을 분리해라

전체 코드

import sys
from copy import deepcopy

n, m , k, c = list(map(int,sys.stdin.readline().rstrip("\n").split()))
# 격자의 크기 n, 박멸이 진행되는 년 수 m, 제초제의 확산 범위 k, 제초제가 남아있는 년 수 c
world = []
for _ in range(n) :
    world.append(list(map(int,sys.stdin.readline().rstrip("\n").split())))
zecho = [[0 for _ in range(n)] for _ in range(n)]

result = 0
d_x = [-1,0,1,0]
d_y = [0,1,0,-1]
c_x = [-1,1,1,-1]
c_y = [1,1,-1,-1]


def grow() :
    global count_world
    for i in range(n) :
        for j in range(n) :
            
            if world[i][j] <= 0 :
                if world[i][j]==-1 :
                    count_world[i][j] = -1
                continue

            for d in range(4) :
                n_x = i+d_x[d]
                n_y = j+d_y[d]
                if 0<=n_x<n and 0<=n_y<n and world[i][j]!=0 and world[i][j]!=-1:
                    if world[n_x][n_y]==0 :
                        # 이후 번식에서 쓸 count
                        if zecho[n_x][n_y]==0 : 
                            count_world[i][j]+=1
                    elif world[n_x][n_y]==-1 :
                        continue
                    else : #world[n_x][n_y]==1
                        world[i][j]+=1
            if count_world[i][j]==0:
                count_world[i][j]=-1

# count_world : 주변 심을 수 있는 개수 카운팅
def plus() :
    global count_world
    for i in range(n) :
        for j in range(n) :
            if world[i][j]==0 or world[i][j]==-1 :
                continue
            for d in range(4) :
                n_x = i+d_x[d]
                n_y = j+d_y[d]
                # 비어있는 지대에 제초제도 없고 벽도 아니야. 나무의 유무는
                if 0<=n_x<n and 0<=n_y<n and count_world[n_x][n_y]==0 and count_world[i][j]!=0 and zecho[n_x][n_y]==0:
                    world[n_x][n_y] += world[i][j]//count_world[i][j]
    

def calJecho() :
    max_n, r_x, r_y = 0,0,0
    for i in range(n) :
        for j in range(n) :
            if world[i][j]==0 or world[i][j]==-1 :
                continue
            zecho=world[i][j]
            for d in range(4) :
                for cr in range(1,k+1) :
                    n_x = i+c_x[d]*cr
                    n_y = j+c_y[d]*cr
                    if 0<=n_x<n and 0<=n_y<n :
                        if world[n_x][n_y]<=0:
                            break
                        zecho+=world[n_x][n_y]
            if max_n<zecho:
                max_n = zecho
                r_x,r_y = i,j
    if max_n ==0:
        return -1,-1
    return r_x, r_y

def jecho(r_x, r_y) :
    kill = world[r_x][r_y]
    for i in range(n) :
        for j in range(n) :
            if zecho[i][j]!=0 :
                zecho[i][j]-=1

    zecho[r_x][r_y]=c
    world[r_x][r_y]=0
    for d in range(4) :
        for cr in range(1,k+1) :
            n_x = r_x+c_x[d]*cr
            n_y = r_y+c_y[d]*cr
            if 0<=n_x<n and 0<=n_y<n:
                # if world[n_x][n_y]==-1:
                #     break
                if world[n_x][n_y]<=0 :
                    zecho[n_x][n_y]=c
                    break
                zecho[n_x][n_y]=c
                kill+=world[n_x][n_y]
                world[n_x][n_y]=0 # 못 만들게 해야 돼
    return kill

for t in range(m) :
    count_world = [[0 for _ in range(n)] for _ in range(n)]
    grow()
    plus()
    r_x, r_y = calJecho()
    if r_x<0 and r_y<0 :
        continue 
    result += jecho(r_x, r_y)
print(result)