[백준 21611번] 마법사 상어와 블리자드 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [0,1,0,-1]
dx = [-1,0,1,0]

def boom(seq):
  global result,boomed
  newseq = []
  x = 0
  while x<len(seq):
    n = seq[x]
    cnt = 1
    while x+cnt<len(seq) and seq[x+cnt]==n:
      cnt += 1
    if cnt >= 4:
      result += n*cnt
      boomed = True
    else:
      for i in range(cnt):
        newseq.append(n)
    x += cnt
  return newseq

def newboard():
  global boomed
  seq = []
  for i in range(1,N*N):
    y,x = Index[i]
    if board[y][x]:
      seq.append(board[y][x])
  while True:
    boomed = False
    seq = boom(seq)
    if boomed:
      continue
    break

  dq = deque()
  x = 0
  while x<len(seq):
    n = seq[x]
    cnt = 1
    while x+cnt<len(seq) and seq[x+cnt]==n:
      cnt += 1
    dq.append(cnt)
    dq.append(n)
    x += cnt

  newboard = [[0]*N for i in range(N)]
  for i in range(1,len(dq)+1):
    if i>=N*N:
      break
    y,x = Index[i]
    newboard[y][x] = dq.popleft()
  return newboard      

N,M = map(int,input().split())

board = []
for i in range(N):
  board.append([*map(int,input().split())])
  
magic = []
for i in range(M):
  d,s = map(int,input().split())
  if d == 3:
    magic.append((0,s))
  elif d == 2:
    magic.append((1,s))
  elif d == 4:
    magic.append((2,s))
  else:
    magic.append((3,s))

Index = [(N//2,N//2)]
d = 0
c = 1
for i in range(N//2*2):
  for j in range(2):
    for k in range(c):
      y,x = Index[-1]
      y1,x1 = y+dy[d],x+dx[d]
      Index.append((y1,x1))
    d = (d+1)%4
  c += 1
for k in range(c-1):
  y,x = Index[-1]
  y1,x1 = y+dy[d],x+dx[d]
  Index.append((y1,x1))

result = 0
for d,s in magic:
  y = x = N//2
  for i in range(s):
    y += dy[d]
    x += dx[d]
    board[y][x] = 0
  board = newboard()

print(result)

오늘도 쉽고 오래걸리는 구현문제이다.

 

간단하게 설명하면

1. 소용돌이 모양의 순서에 대한 Index를 먼저 만들어준다.

2. 블리자드 마법 시전

3. board의 숫자들을 Index의 순서대로 seq에 집어넣는다.

4. boom 함수를 통해 4개 이상의 구슬이 존재하면 폭발시키고 newseq를 만들어 갱신한다.

5. boom 함수에서 변화가 더이상 나타나지 않으면 dq에 개수와 숫자로 이루어진 새로운 수열을 저장한다.

6. Index의 순서대로 board에 기입한다.

 

이때 3~4번에서 boom을 하는 과정을 한번에 하기 위해서 stack을 이용해서는 안된다. 모든 폭발은 한번에 일어나야하고, 폭발이 일어난 후, 2차, 3차, 4차 폭발이 일어나야 한다.

테스트 케이스에 이렇게 구현했을 때의 반례가 존재하지 않아서 애먹었다...

 

 

오늘의 교훈) 구현문제 실수하지 말자