나무박멸

# 입력
N, M, K, C = map(int, input().split())
graph = [[] for _ in range(N)]
temp = [[0 for _ in range(N)] for _ in range(N)]
isPolluted = [[0 for _ in range(N)] for _ in range(N)]
pollute = [[0 for _ in range(N)] for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
answer = 0
for i in range(N):
    graph[i] = list(map(int, input().split()))


def init():
    global isPolluted, pollute, temp
    pollute = [[0 for _ in range(N)] for _ in range(N)]
    temp = [[0 for _ in range(N)] for _ in range(N)]

    for row in range(N):
        for col in range(N):
            if isPolluted[row][col] > 0:
                isPolluted[row][col] -= 1


while M:
    # 성장 (인접 4칸)
    for r in range(N):
        for c in range(N):
            if graph[r][c] > 0:
                treeCnt = 0
                for xx, yy in zip(dx, dy):
                    curX, curY = r + xx, c + yy
                    if 0 <= curX < N and 0 <= curY < N:
                        if graph[curX][curY] > 0:
                            treeCnt += 1
                graph[r][c] += treeCnt

    # 번식
    for r in range(N):
        for c in range(N):
            if graph[r][c] > 0:
                blankCnt = 0
                # 번식 가능 칸 파악
                for xx, yy in zip(dx, dy):
                    curX, curY = r + xx, c + yy
                    if 0 <= curX < N and 0 <= curY < N:
                        if graph[curX][curY] == 0 and isPolluted[curX][curY] == 0:
                            blankCnt += 1
                val = 0
                if blankCnt > 0:
                    val = graph[r][c] // blankCnt
                # 임시 배열에 저장
                for xx, yy in zip(dx, dy):
                    curX, curY = r + xx, c + yy
                    if 0 <= curX < N and 0 <= curY < N:
                        if graph[curX][curY] == 0 and isPolluted[curX][curY] == 0:
                            temp[curX][curY] += val
    # 원본 배열에 반영
    for r in range(N):
        for c in range(N):
            if temp[r][c] > 0:
                graph[r][c] = temp[r][c]

    # 제초제 최대 피해 선정
    maxDamage = 0
    maxX, maxY = -1, -1
    for r in range(N-1, -1, -1):
        for c in range(N-1, -1, -1):
            ru, lu, rd, ld = True, True, True, True
            if graph[r][c] > 0:
                pollute[r][c] += graph[r][c]
                for x in range(1, K + 1):
                    cx, cy = r + x, c + x
                    cxx, cyy = r + x, c - x
                    cxu, cyd = r - x, c + x
                    cxxu, cyyd = r - x, c - x
                    if rd and 0 <= cx < N and 0 <= cy < N:
                        if graph[cx][cy] > 0:
                            pollute[r][c] += graph[cx][cy]
                        else:
                            rd = False
                    if ld and 0 <= cxx < N and 0 <= cyy < N:
                        if graph[cxx][cyy] > 0:
                            pollute[r][c] += graph[cxx][cyy]
                        else:
                            ld = False
                    if ru and 0 <= cxu < N and 0 <= cyd < N:
                        if graph[cxu][cyd] > 0:
                            pollute[r][c] += graph[cxu][cyd]
                        else:
                            ru = False
                    if lu and 0 <= cxxu < N and 0 <= cyyd < N:
                        if graph[cxxu][cyyd] > 0:
                            pollute[r][c] += graph[cxxu][cyyd]
                        else:
                            lu = False

            if maxDamage <= pollute[r][c]:
                maxDamage = pollute[r][c]
                maxX, maxY = r, c

    # 제초제 작업 진행 (제초제 효력 C년)
    if graph[maxX][maxY] > 0:
        answer += graph[maxX][maxY]
        graph[maxX][maxY] = 0
    isPolluted[maxX][maxY] = C + 1
    ru, lu, rd, ld = True, True, True, True
    for x in range(1, K + 1):
        cx, cy = maxX + x, maxY + x
        cxx, cyy = maxX + x, maxY - x
        cxu, cyd = maxX - x, maxY + x
        cxxu, cyyd = maxX - x, maxY - x
        if rd and 0 <= cx < N and 0 <= cy < N:
            if graph[cx][cy] > 0:
                answer += graph[cx][cy]
                graph[cx][cy] = 0
                isPolluted[cx][cy] = C + 1
            else:
                isPolluted[cx][cy] = C + 1
                rd = False
        if ld and 0 <= cxx < N and 0 <= cyy < N:
            if graph[cxx][cyy] > 0:
                answer += graph[cxx][cyy]
                graph[cxx][cyy] = 0
                isPolluted[cxx][cyy] = C + 1
            else:
                isPolluted[cxx][cyy] = C + 1
                ld = False
        if ru and 0 <= cxu < N and 0 <= cyd < N:
            if graph[cxu][cyd] > 0:
                answer += graph[cxu][cyd]
                graph[cxu][cyd] = 0
                isPolluted[cxu][cyd] = C + 1
            else:
                isPolluted[cxu][cyd] = C + 1
                ru = False
        if lu and 0 <= cxxu < N and 0 <= cyyd < N:
            if graph[cxxu][cyyd] > 0:
                answer += graph[cxxu][cyyd]
                graph[cxxu][cyyd] = 0
                isPolluted[cxxu][cyyd] = C + 1
            else:
                isPolluted[cxxu][cyyd] = C + 1
                lu = False

    init()
    M -= 1
print(answer)

G4

이제 삼성에 이정도 수준의 문제가 나온다고 하면 꽤 쉽게 느껴지는 것 같다.

기존에 구현으로 어려웠던 문제는 보통 1~2 단계의 과정이 여기에서 더 있었다.

예를 들면, 이 문제는 나무성장 -> 번식 -> 제초제 3단계의 큰 과정 한 개에 대한 구현이었다면 어려운 문제는 큰 과정 한 개 가 여기에 이어서 나왔었다.

아무튼 이 정도의 문제로 우선 유형에 익숙해지고, 빠르고 정확하게 푸는 연습을 하는 것이 좋을 것 같다.

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