[CodeTree] 미로 타워 디펜스 - 삼성 SW 역량테스트 2021 상반기 오후 2번 문제

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

 

문제 분석

• N*N으로 이뤄진 나선형 미로에 1/2/3번 몬스터가 침략을 진행하고 있음.
• 문제는 아래 로직대로 작동.
  • player는 상하좌우 방향 중 주어진 공격 칸 수 만큼 몬스터를 없앨 수 있음. 공격하는 칸의 수는 1 ~ N//2사이의 값이며, 배열의 범위를 넘어가 값을 제거하는 Case는 없음.
  • 지워진 칸이 존재할 경우, 뒤에 있는 배열 값들을 앞으로 채워나가는 과정 수행.
  • 연속되는 몬스터 그룹의 크기가 4이상일 경우 제거하며, 지워진 자리에 다시 뒤의 배열 값을 채워나가고 크기가 4이상인 몬스터 그룹이 존재하지 않을 때 까지 반복하여 수행.
  • 위 과정이 종료된 후, 차례대로 나열했을 때 같은 숫자끼리 그룹핑 진행.
  • 예시로 [1, 2, 2, 3, 1, 3, 1]의 배열일 경우, [1, 1, 2, 2, 1, 3, 1, 1, 1, 3]으로 변경하며 이는 [연속되는 숫자 수, 숫자]의 연속적인 값과 동일함.
• player가 공격할 때, 혹은 4개 이상의 몬스터 그룹을 제거할 때, 격자 칸에 존재하는 값을 score로 얻게 됨.
• m번의 사용자 공격, 4개 이상 그룹 처리 그리고 새 배열 생성 과정을 거친 후 최종 score를 Return하는 문제.

 

문제 접근

• 일반 row / col 순서대로가 아니라, 나선형 모양의 배열로써 작동함. 따라서, 두 가지의 자료구조 정의.
  • 나선형 순서대로 값을 관리하는 vq 배열 생성.
  • N*N 격자의 좌표 -> vq의 index로 접근할 수 있는 딕셔너리  생성.
  • vq 배열은 매 turn마다 갱신되며, 딕셔너리는 고정.
• player 공격
  • player가 있는 중심점을 기준으로 방향 + 크기에 맞는 공격 과정을 수행.
  • 제거할 idx를 선정할 때, 위 생성한 딕셔너리를 활용함.
  • 만약 공격 범위가 2이상일 경우, 앞의 idx를 제거하면 그 후에 있는 값을 제거할 때는 기존 idx에서 -1을 한 배열의 값을 pop해야 앞서 삭제된 idx로 발생하는 무결성을 해결할 수 있음.
• 4개 이상의 몬스터 그룹 탐색 / 제거
  • 선형 탐색을 진행하며 제거할 그룹이 있는지 판단하는 로직 구현.
  • 제거할 그룹이 있다면 제거 후 값을 갱신하는 방식을 채택하며, 없을 시에 종료.
• 새 배열 생성
  • 문제에 제시된 대로 [그룹 크기, 숫자]가 연속적으로 생성되도록 새 배열 생성.
  • 범위를 넘어가는 배열의 경우 따로 사용하지 않고 삭제하는 과정이 필요했기에, try - except 구문을 활용하여 (n**2)-1의 크기를 넘어갈 경우 종료되도록 구현.

 

소스 코드

# define lib
from collections import deque, defaultdict


# set value from input
n, m = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
cmds = [list(map(int, input().split())) for _ in range(m)]

# initialize
rot_direc = [(0, -1), (1, 0), (0, 1), (-1, 0)]
rot_flag = [i for i in range(1, n) for _ in range(2)] + [n-1]
vq, pt_to_idx = [], defaultdict(int)
sx, sy, sd = n//2, n//2, 0

idx = 0
for rot in rot_flag:
    while rot:
        sx, sy = sx+rot_direc[sd][0], sy+rot_direc[sd][1]
        vq.append(field[sx][sy])
        pt_to_idx[(sx, sy)] = idx
        idx, rot = idx+1, rot-1
    sd = (sd+1)%4

# attack and remove and generate
score = 0
player_direc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for ad, ap in cmds:
    px, py = n//2, n//2

    # attack
    attack_idx = [-i for i in range(ap)]
    while ap > 0:
        ax, ay = px+player_direc[ad][0]*ap, py+player_direc[ad][1]*ap
        attack_idx[ap-1] += pt_to_idx[(ax, ay)]
        ap -= 1
    
    # remove attack idx
    for idx in attack_idx:
        score += vq[idx]
        vq.pop(idx)
        vq.append(0)
    
    # remove group which size >= 4
    while True:
        exit_flag, prev = True, 0
        for idx in range(1, n**2-1):
            if vq[prev] == vq[idx]:
                continue
            if idx-prev >= 4 and vq[prev] != 0:
                score += vq[prev] * (idx-prev)
                for ridx in range(prev, idx):
                    vq[ridx] = 0
                exit_flag = False
            prev = idx
        else:
            if idx-prev >= 4 and vq[prev] != 0:
                score += vq[prev] * (idx-prev)
                for ridx in range(prev, idx):
                    vq[ridx] = 0
                exit_flag = False

        if exit_flag:
            break

        new_queue, new_qidx = [0]*(n**2-1), 0
        for value in vq:
            if value == 0:
                continue
            new_queue[new_qidx] = value
            new_qidx += 1
        vq = new_queue

    # make new_queue
    new_queue, new_qidx, prev = [0]*(n**2-1), 0, 0
    for idx in range(1, n**2-1):
        if vq[prev] == vq[idx]:
            continue
        try:
            new_queue[new_qidx] = idx-prev
            new_queue[new_qidx+1] = vq[prev]
            new_qidx += 2
            prev = idx
        except:
            break
    vq = new_queue
print(score)

• 풀이 시간: 60분
• 제출 시간: 1회