[코드트리] 미로 타워 디펜스 - python

↑문제 링크: https://www.codetree.ai/frequent-problems/maze-tower-defense/description

코드트리

제일 문제가 되는 부분은 나선형으로 2차원 Array를 어떻게 방문할지였습니다. 문제에서는 중심을 시작으로 ←, ↓, →, ↑ 순으로 진행하게 되는데 저는 (0, 0)을 시작으로 →, ↓, ←, ↑ 순으로 탐색한 다음 순서를 뒤집어서 방문 순서를 저장해 두었습니다. 이렇게 변형한 이유는 변형된 순서로 탐색을 하게 되면 다음 위치가 격자를 벗어나거나 이미 방문한 위치이면 방향을 을 전환하면 되기 때문에 방향 변경시점을 파악하기 쉽기 때문입니다. 그 다음은 폭탄 터뜨리고 중력 적용하기와 비슷합니다. 공격 방향으로 몬스터를 제거하고 이미 저장해놓은 방문 순서를 따라 몬스터들을 1차원 리스트로 뽑은 다음 4마리 연속 존재하는 몬스터 제거하고 다음 몬스터를 찾아서 마찬가지로 저장해놓은 방문 순서에 따라 세팅해주면 됩니다.

 

걸린 시간: 1시간 7분 22초

# 문제링크: https://www.codetree.ai/frequent-problems/maze-tower-defense/description
import sys

sys.stdin = open('input.txt')
EMPTY = 0

n, m = tuple(map(int, input().split()))
center = (n // 2, n // 2)

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

attack = [
    tuple(map(int, input().split()))
    for _ in range(m)
]

temp = [
    [False] * n
    for _ in range(n)
]

order = []

dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

y, x = 0, 0
dir = 0

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

# 미로 방문 순서
while True:
    if (y, x) == center:
        break
    temp[y][x] = True
    order.append((y, x))

    ny = y + dys[dir]
    nx = x + dxs[dir]

    if not inRange(ny, nx) or temp[ny][nx]:
        dir = (dir + 1) % 4

        y = y + dys[dir]
        x = x + dxs[dir]
    else:
        y = ny
        x = nx

order = list(reversed(order))

def attack_monster(d, p):
    y, x = center
    score = 0

    while p:
        p -= 1
        y = y + dys[d]
        x = x + dxs[d]

        if not inRange(y, x):
            break

        score += board[y][x]
        board[y][x] = EMPTY

    return score

def pull():
    monsters = []
    # 몬스터들을 담음
    for y, x in order:
        monsters.append(board[y][x])

    tail_idx = 0

    for i in range(len(monsters)):
        if monsters[i] != EMPTY:
            monsters[tail_idx] = monsters[i]
            tail_idx += 1

    # 다 채우지 못한 부분들도 빈 곳으로 초기화
    while tail_idx < len(monsters):
        monsters[tail_idx] = EMPTY
        tail_idx += 1

    return monsters


def check_sequence(monsters):
    global answer

    while True:
        cnt = 1
        cur = monsters[0]
        found_sequnce = False
        final_monsters = []
        temp = [monsters[0]]

        for i in range(1, len(monsters)):
            if cur != monsters[i]:
                # 4미만인 경우에만 추가
                if cnt < 4:
                    final_monsters += temp
                # 4이상인 경우에는 점수
                else:
                    found_sequnce = True
                    answer += (cur * cnt)

                temp = [monsters[i]]
                cnt = 1
                cur = monsters[i]
            else:
                cnt += 1
                temp.append(monsters[i])


        if cnt < 4:
            final_monsters += temp
        else:
            found_sequnce = True
            answer += (cur * cnt)

        # 4개 연속을 찾지 못한 경우
        if not found_sequnce:
            break

        monsters = final_monsters

    return final_monsters

def get_next_monsters(monsters):
    cnt = 1
    cur = monsters[0]

    next_monsters = []
    for i in range(1, len(monsters)):
        if cur != monsters[i]:
            next_monsters.append(cnt)
            next_monsters.append(cur)
            cnt = 1
            cur = monsters[i]
        else:
            cnt += 1
    next_monsters.append(cnt)
    next_monsters.append(cur)

    return next_monsters

def set_board(monsters):
    for i, (y, x) in enumerate(order):
        if i >= len(monsters):
            board[y][x] = EMPTY
        else:
            board[y][x] = monsters[i]

answer = 0

def simulate(d, p):
    global answer
    # 몬스터 공격 and 점수
    answer += attack_monster(d, p)

    #당기기
    monsters = pull()

    # 4번이상 나오는 몬스터 제거
    alive_monsters = check_sequence(monsters)

    # 다음 몬스터 생성
    next_monsters = get_next_monsters(alive_monsters)

    # 미로 세팅
    set_board(next_monsters)

for d, p in attack:
    simulate(d, p)

print(answer)