[코드트리/삼성SW역량테스트] 미로 타워 디펜스 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/maze-tower-defense

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

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:38:41

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

사실 1년여 전에 풀었던 문제. 백준에도 똑같은 문제가 올라와 있다. 그래서 백준에도 똑같은 문제를 포스팅할 것인지, 애초에 코드트리에서 이미 본 문제를 다시 풀이하는 게 옳은지... 고민했다. 동일 문제는 링크로 정리하도록 하고, 복습 겸 내 코딩 스타일이 1년 전과 비교해서 어떻게 변화했는지를 체크하는 용도로 다시 한 번 도전해보기로 했다.

 

https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

 

몬스터를 나선형으로 일일히 탐색하느니, 몬스터를 하나의 리스트로 두고 공격 방향 당 리스트 좌표를 호출해서 처리하는 편이 낫다. 나선형 탐색에 대한 구현 부분만 주의하면 되는 문제.

 

풀이 코드(1년전)

 

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N, M = map(int,input().split())
order = []
x, y = N//2, N//2
c, cnt, dir = 0, 1, 0
blizaard = [[] for _ in range(5)]

while True:
  for _ in range(cnt):
    x, y = x+dx[dir], y+dy[dir]
    order.append((x, y))
    if x == 0 and y == 0 : break
    elif x == N//2 :
      if y > N//2 :
        blizaard[2].append(c)
      else :
        blizaard[1].append(c)
    elif y == N//2 :
      if x > N//2 :
        blizaard[4].append(c)
      else :
        blizaard[3].append(c)
    c += 1
        
  if x == 0 and y == 0 : break
  dir = (dir+1)%4
  for _ in range(cnt):
    x, y = x+dx[dir], y+dy[dir]
    order.append((x, y))
    if x == N//2 :
      if y > N//2 :
        blizaard[2].append(c)
      else :
        blizaard[1].append(c)
    elif y == N//2 :
      if x > N//2 :
        blizaard[4].append(c)
      else :
        blizaard[3].append(c)
    c += 1
  cnt += 1
  dir = (dir+1)%4

map_lst = [list(map(int,input().split())) for _ in range(N)]
lst = [map_lst[y][x] for x, y in order]
ans, end = 0, N**2-1
for _ in range(M):
  d, s = map(int,input().split())
  for i in range(s):
    lst[blizaard[d][i]] = 0
  lst.sort(key = lambda x : x == 0)

  while True:
    flg = True
    cnt, start, base = 1, 0, lst[0]
    for i in range(1, end):
      if base == lst[i] :
        cnt += 1
      else :
        if cnt >= 4 :
          flg = False
          ans += cnt*base
          for j in range(start, i):
            lst[j] = 0
        cnt, start, base = 1, i, lst[i]
      if lst[i] == 0: break
      if i == end-1 and cnt >= 4:
          flg = False
          ans += cnt*base
          for j in range(start, i+1):
            lst[j] = 0
    lst.sort(key = lambda x : x == 0)
    if flg : break
  tmp = []
  cnt, base = 1, lst[0]
  for i in range(1, end):
    if base == lst[i] :
      cnt += 1
    else :
      tmp += [cnt, base]
      cnt, base = 1, lst[i]
    if lst[i] == 0 : break
    if i == end-1 :
      tmp += [cnt, base]
  if len(tmp) < len(lst) :
    tmp += [0]*(len(lst)-len(tmp))
  elif len(tmp) > len(lst) :
    tmp = tmp[:end]
  lst = tmp
print(ans)

 

풀이 코드

import sys
input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]

n, m = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(n)]
da = [list() for _ in range(4)]
monster_queue = list()
r, c = n // 2, n // 2
d, t, l = 0, 1, 1
ans = 0

for i in range(n**2) :
    r += dr[d]
    c += dc[d]
    t -= 1
    if t == 0 :
        d = (d + 1) % 4
        if d in [0, 2] :
            l += 1
        t = l
    if monsters[r][c] :
        monster_queue.append(monsters[r][c])
    if r == n // 2 :
        idx = 2 if c < n // 2 else 0
        da[idx].append(i)
    if c == n // 2 :
        idx = 3 if r < n // 2 else 1
        da[idx].append(i)


def attack(d, p) :
    global monster_queue, ans
    for i in da[d][:p] :
        if i >= len(monster_queue) :
            break
        ans += monster_queue[i]
        monster_queue[i] = 0
    
    monster_queue = [ x for x in monster_queue if x > 0 ]

def match() :
    global monster_queue, ans
    if len(monster_queue) < 4 :
        return

    flg = True
    while flg :
        flg = False
        prev, q = monster_queue[0], [0]
        for i in range(1, len(monster_queue)) :
            if prev == monster_queue[i] :
                q.append(i)
            elif len(q) >= 4 :
                flg = True
                ans += prev*len(q)
                for j in q :                    
                    monster_queue[j] = 0
                prev, q = monster_queue[i], [i]
            else :
                prev, q = monster_queue[i], [i]
        if len(q) >= 4 :
            flg = True
            ans += prev*len(q)
            for j in q :                    
                monster_queue[j] = 0
        if flg :
            monster_queue = [ x for x in monster_queue if x > 0 ]

def expand() :
    global monster_queue
    if not monster_queue :
        return
    new_monster_queue = list()
    prev, cnt = monster_queue[0], 1
    for monster in monster_queue[1:] :
        if monster == prev :
            cnt += 1
        else :
            new_monster_queue += [cnt, prev]
            prev, cnt = monster, 1
    new_monster_queue += [cnt, prev]
    monster_queue = new_monster_queue[:n**2]

for _ in range(m) :
    d, p = map(int, input().split())
    attack(d, p)
    match()
    expand()
print(ans)

풀이 완료!