[알고리즘] 나무 타이쿤 (삼성SW역량테스트 2021 상반기 오후 1번 기출 - 시뮬레이션)

나무 타이쿤

삼성 SW역량테스트 2021 상반기 오후 1번 문제이다.

문제 출처는 아래 코드 트리 링크이다.

 

https://www.codetree.ai/training-field/frequent-problems/tree-tycoon

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

dx, dy techinque를 기반으로 한 시뮬레이션 문제로, 백준 기준으로 치면 Gold 5 등급 수준의 기출 문제이다.

 

 

def get_nutrition(lib, r, c):
    arr = []
    n = len(lib[0])
    for i in range(r, r - 2, -1):
        for j in range(c, c + 2):
            n_r, n_c = get_over_grid(i, j, n)
            arr.append((n_r, n_c))
    return arr


def get_over_grid(a, b, n):
    if a >= n:
        a = (a - n)
    elif a < 0:
        a = (n + a)

    if b >= n:
        b = (b - n)
    elif b < 0:
        b = (n + b)

    return a, b

def move(nutritions, d, p, num):
    move_types = [(0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1)]

    for n in nutritions:
        n_r = n[0]
        n_c = n[1]
        for j in range(p):
            n_r += move_types[d - 1][0]
            n_c += move_types[d - 1][1]
        n[0], n[1] = get_over_grid(n_r, n_c, num)


def inject(lib, nutritions):
    for n in nutritions:
        lib[n[0]][n[1]] += 1


def get_count_diagnoal(lib, r, c, n):
    move_types = [(1, 1), (1, -1), (-1, -1), (-1, 1)]
    cnt = 0
    for type in move_types:
        n_r, n_c = r + type[0], c + type[1]
        if n_r < 0 or n_r >= n or n_c < 0 or n_c >= n:
            continue
        else:
            if lib[n_r][n_c] > 0:
                cnt += 1
    return cnt


def inject_by_diaganoal(lib, nutritions):
    num = len(lib[0])
    nut_dic = {i: 0 for i in range(len(nutritions))}

    for i in range(len(nutritions)):
        nut_dic[i] = get_count_diagnoal(lib, nutritions[i][0], nutritions[i][1], num)

    for i in range(len(nutritions)):
        lib[nutritions[i][0]][nutritions[i][1]] += nut_dic[i]


def cut_and_new(lib, nutritions):
    num = len(lib[0])
    new_nutritions = []

    for i in range(num):
        for j in range(num):
            if [i, j] not in nutritions and lib[i][j] >= 2:
                lib[i][j] -= 2
                new_nutritions.append([i, j])

    return new_nutritions


def count_libs(lib):
    cnt = 0
    n = len(lib[0])
    for i in range(n):
        cnt += sum(lib[i])
    return cnt

def solution():
    n, m = map(int, input().split())
    lib = [list(map(int, input().split())) for _ in range(n)] 
    nutritions = [[n - 1, 0], [n - 2, 0], [n - 1, 1], [n - 2, 1]] 

    for _ in range(m):
        d, p = map(int, input().split())

        move(nutritions, d, p, n)
        inject(lib, nutritions)
        inject_by_diaganoal(lib, nutritions)
        nutritions = cut_and_new(lib, nutritions)

    print(count_libs(lib))

solution()