이번 문제는 삼성 기출 문제로 구현과 시뮬레이션에 속하는 문제이다. 격자에 초기 데이터를 입력받고, 상어의 위치를 기준으로 소용돌이치며 나가는 인덱스의 순서에 대한 리스트를 get_nums 함수를 통해 먼저 만들었다. 그리고 상어가 파괴시키는 함수 destroy, 구슬들이 밀려 움직이는 함수 move, 구슬들이 폭발하는 함수 explode, 구슬들의 그룹을 ab로 만드는 함수 to_ab를 작성하였다.

get_nums():
BFS를 통해 (0, 0)부터 순회하며 범위를 벗어나거나 다음 위치가 이미 방문한 경우 방향을 바꾸도록 하여 밖에서 상어로 들어가는 순의 리스트 idxs를 만든다. (여기서 만들어진 인덱스는 거꾸로 뒤집어 사용된다.)
destroy(command):
상어가 명령에 따라 주어진 방향의 구슬을 파괴하는 함수로, (n//2, n//2)를 기준으로 주어진 방향과 거리만큼의 구슬을 0으로 바꾼다.
move():
구슬이 밀리는 것을 구현한 함수로, idxs를 순회하며 만약 현재 위치가 0일 경우, 현재 위치를 저장하는 변수 cur을 만들고, 현재 위치부터 idxs를 다시 순회하며 0이 아닌 경우에만 cur과 그 위치의 값을 바꾼다. 그리고 cur을 1 증가시킨다.
explode():
구슬이 폭발하는 것을 구현한 함수로, idxs를 순회하며 이전 위치와 값이 같을 경우, 해당 위치의 인덱스를 cnt리스트에 담고, 그렇지 않을 경우 cnt리스트의 길이가 4 이상이라면 cnt를 순회하며 해당 리스트의 값을 0으로 바꾸며 정답 리스트의 수를 증가시켜주었다. 그리고 현재 인덱스를 나타내는 변수 i를 cnt의 길이만큼 증가시켰다. 0을 만나면 이미 구슬이 밀려있는 상태이기 때문에 더 이상 순회할 필요가 없으므로 순회를 종료하였다.
to_ab():
구슬의 그룹을 찾아 a, b로 다시 담는 것을 구현한 함수로, idxs를 순회하며 이전값과 현재값이 같을 경우 cnt변수를 증가시키고, 그렇지 않다면 groups리스트에 (cnt, 이전 값)의 형태로 값을 담는다. 그리고 grid를 0으로 채워진 리스트로 초기화하고, groups리스트를 순회하며 값들을 채워넣었다.
예제 4번이 정답이 나오지 않아 무엇이 잘못되었는지 계속 살펴보았지만, 찾지 못하였다. 그러던 중, 문제를 다시 읽어보고 문제를 알 수 있었다. 폭발과 구슬의 이동은 더 이상의 폭발이 일어날 수 없을 때까지 반복되어야 했는데, 여기에 대한 함수 호출을 잘못했기 때문이었다. 이를 while문으로 호출하도록 변경하였고, 정답처리를 받을 수 있었다.

Code

import copy
from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
commands = []
for _ in range(m):
    di, si = map(int, input().split())
    commands.append((di-1, si))
nums = [[0 for _ in range(n)] for _ in range(n)]
idxs = []
center = (n//2, n//2)
marbles = [0, 0, 0, 0]
ndy, ndx = [0, 1, 0, -1], [1, 0, -1, 0]
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
def get_nums():
    q = deque()
    q.append((0, 0, n*n-1))
    nums[0][0] = n*n-1
    d = 0
    while q:
        y, x, num = q.popleft()
        idxs.append((y, x))
        if (y, x) == center:
            break
        ny, nx = y+ndy[d], x+ndx[d]
        if 0 <= ny < n and 0 <= nx < n and not nums[ny][nx]:
            nums[ny][nx] = num-1
            q.append((ny, nx, num-1))
        else:
            d = (d+1)%4
            ny, nx = y+ndy[d], x+ndx[d]
            nums[ny][nx] = num-1
            q.append((ny, nx, num-1))
def destroy(command):
    d, s = command
    y, x = center
    for i in range(1, s+1):
        ny, nx = y+(dy[d]*i), x+(dx[d]*i)
        if 0 <= ny < n and 0 <= nx < n:
            grid[ny][nx] = 0
def move():
    for i in range(1, len(idxs)-1):
        if not grid[idxs[i][0]][idxs[i][1]]:
            cur = i
            for j in range(i+1, len(idxs)):
                if grid[idxs[j][0]][idxs[j][1]]:
                    grid[idxs[cur][0]][idxs[cur][1]], grid[idxs[j][0]][idxs[j][1]] = grid[idxs[j][0]][idxs[j][1]], 0
                    cur += 1
            break
def explode():
    i = 1
    while i < len(idxs)-1:
        if grid[idxs[i][0]][idxs[i][1]]:
            std = grid[idxs[i][0]][idxs[i][1]]
            cnt = [(idxs[i][0], idxs[i][1])]
            for j in range(i+1, len(idxs)):
                if grid[idxs[j][0]][idxs[j][1]] == std:
                    cnt.append((idxs[j][0], idxs[j][1]))
                else:
                    break
            if len(cnt) >= 4:
                for y, x in cnt:
                    marbles[grid[y][x]] += 1
                    grid[y][x] = 0
            i += len(cnt)
        else:
            break
def to_ab():
    global grid
    groups = []
    tmp = grid[idxs[1][0]][idxs[1][1]]
    cnt = 0
    for y, x in idxs[1:]:
        if grid[y][x] == tmp:
            cnt += 1
            tmp = grid[y][x]
        else:
            groups.append((cnt, tmp))
            cnt = 1
            tmp = grid[y][x]
    cur = 1
    grid = [[0 for _ in range(n)] for _ in range(n)]
    for a, b in groups:
        if cur > len(idxs)-1:
            break
        grid[idxs[cur][0]][idxs[cur][1]] = a
        cur += 1
        if cur > len(idxs)-1:
            break
        grid[idxs[cur][0]][idxs[cur][1]] = b
        cur += 1
get_nums()
idxs = idxs[::-1]
for i in range(m):
    destroy(commands[i])
    move()
    while True:
        tmp = copy.deepcopy(grid)
        explode()
        move()
        if tmp == grid:
            break
    to_ab()
answer = 0
for i in range(1, 4):
    answer += marbles[i]*i
print(answer)