[코드트리] - 나무박멸

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

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제종류

dx dy technique, simulation

풀이시간

설계: 25분 구현: 120분

풀이방법

문제의 요구사항대로 잘 구현하면 된다. 다만 배열의 값을 바꿔줄 경우 벽인곳의 값은 유지해줘야하는곳에 주의해야한다.

저거 못잡아서 1시간 20분 날려먹었다^^

코드

dx, dy = [-1, 0, 0, 1], [0, 1, -1, 0]
bx, by = [-1, -1, 1, 1], [-1, 1, -1, 1]
WALL = -1


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


def main():
    ans = 0
    n, m, k, cc= map(int, input().split())
    # 나무, 벽 정보
    arr = [list(map(int, input().split())) for i in range(n)]
    # 제초제 정보
    barr = [[-1] * n for i in range(n)]

    for year in range(m):
        # 나무 성장 (벽이 아닌곳, 제초제가 아닌곳)
        for r in range(n):
            for c in range(n):
                # 벽이 아니고, 제초제가 아닐 경우

                if arr[r][c] > 0 and barr[r][c] < year:
                    nc = 0
                    for ddx, ddy in zip(dx, dy):
                        nx, ny = r + ddx, c + ddy
                        if not in_range(nx, ny, n):
                            continue
                        # 제초제고, 벽일 경우
                        if barr[nx][ny] >= year or arr[nx][ny] <= 0:
                            continue
                        nc += 1
                    arr[r][c] += nc
        # 나무 번식 (벽, 다른나무, 제초제가 없을때)
        # (x,y,diff)
        spread_info = []
        for r in range(n):
            for c in range(n):
                # 벽이 아니고, 제초제가 아닐 경우
                if arr[r][c] > 0 and barr[r][c] < year:
                    nc = 0
                    for ddx, ddy in zip(dx, dy):
                        nx, ny = r + ddx, c + ddy
                        if not in_range(nx, ny, n):
                            continue
                        # 제초제고, 벽 혹은 다른 나무일경우
                        if barr[nx][ny] >= year or arr[nx][ny] != 0:
                            continue
                        nc += 1
                    if nc == 0:
                        continue
                    sdiff = arr[r][c] // nc
                    for ddx, ddy in zip(dx, dy):
                        nx, ny = r + ddx, c + ddy
                        if in_range(nx, ny, n) and arr[nx][ny] == 0 and barr[nx][ny] < year:
                            spread_info.append((nx, ny, sdiff))

        for sx, sy, diff in spread_info:
            arr[sx][sy] += diff

        # 나무 박멸
        death_info = []
        for r in range(n):
            for c in range(n):
                if arr[r][c] <= 0:
                    death_info.append((r, c, 0))
                    continue
                dcnt = arr[r][c]
                for bbx, bby in zip(bx, by):
                    for p in range(1, k + 1):
                        nx, ny = r + bbx * p, c + bby * p
                        if not in_range(nx, ny, n):
                            continue
                        # 벽이거나 제초제가 남아있을경우
                        if arr[nx][ny] <= 0 or year <= barr[nx][ny]:
                            break
                        dcnt += arr[nx][ny]
                death_info.append((r, c, dcnt))

        # 박멸 기준 좌표 정하기
        bsx, bsy, bcnt = sorted(death_info, key=lambda x: (-x[2], x[0], x[1]))[0]
        # 현재 좌표 제초게 갱신
        ans += bcnt
        barr[bsx][bsy] = year + cc
        arr[bsx][bsy] = 0
        for bbx, bby in zip(bx, by):
            for p in range(1, k + 1):
                nx, ny = bsx + bbx * p, bsy + bby * p
                if not in_range(nx, ny, n):
                    continue
                # 벽이거나 나무가 없거나 제초제가 남아있을경우
                if arr[nx][ny] <= 0 or year <= barr[nx][ny]:
                    barr[nx][ny] = year + cc
                    # 박멸
                    if arr[nx][ny] != -1:
                        arr[nx][ny] = 0
                    break
                barr[nx][ny] = year + cc
                arr[nx][ny] = 0

    print(ans)
main()