[코드트리] - 나무 타이쿤

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

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

문제종류

dx dy, simulation

풀이시간

설계: 3분 구현:26분

 

풀이방법

까다로운 요구사항은 없는 문제, 단지 영양제를 투입할때 나무의 성장은 동시에 일어난다는 조건에 주의해야함

 

코드

# 20:28
# → ↗ ↑ ↖ ← ↙ ↓ ↘
dx, dy = [0, -1, -1, -1, 0, 1, 1, 1], [1, 1, 0, -1, -1, -1, 0, 1]
bx, by = [-1, -1, 1, 1], [1, -1, 1, -1]
"""
1. 영양제 이동
2. 영양제 투입, 투입한 영양제 사라짐
3. 리브로수의 대각선으 인접한 방향 리브로수가 있는 만큼 성장
4. 성장한 리브로수 제외하고 2이상 높이인 리브로수의 높이 2를 베고,해당 위치 특수영양제 생성
"""


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


def transpos(x, y, n):
    if x >= n:
        x -= n
    if x < 0:
        x = n + x

    if y >= n:
        y -= n
    if y < 0:
        y = n + y

    return x, y


def main():
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(N)]
    # 영양제의 위치는 겹칠수없음
    yarr = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]]

    dp_arr = []
    for i in range(M):
        d, p = map(int, input().split())
        d -= 1
        dp_arr.append((d, p))

    for turn in range(M):
        # 영양제 이동
        md, mp = dp_arr[turn]
        for yi in range(len(yarr)):
            yx, yy = yarr[yi]
            nx, ny = transpos(yx + dx[md] * mp, yy + dy[md] * mp, N)
            yarr[yi] = [nx, ny]

        diff_arr = []
        grow_set = set()
        for yx, yy in yarr:
            arr[yx][yy] += 1

        for yx, yy in yarr:
            cnt = 0
            for bbx, bby in zip(bx, by):
                nx, ny = yx + bbx, yy + bby
                if in_range(nx, ny, N) and arr[nx][ny] >= 1:
                    cnt += 1
            diff_arr.append((yx, yy, cnt))
            grow_set.add((yx, yy))

        for yx, yy, diff in diff_arr:
            arr[yx][yy] += diff

        next_yarr = []
        for r in range(N):
            for c in range(N):
                if not (r, c) in grow_set and arr[r][c] >= 2:
                    arr[r][c] -= 2
                    next_yarr.append([r, c])
        yarr = next_yarr

    ans = 0
    for x in range(N):
        ans += sum(arr[x])
    print(ans)


main()