[백준] 21611. 마법사 상어와 블리자드

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

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

구슬 탐색을 위한 델타값과 블리자드 마법을 위한 델타값이 다르다는 조건을 제대로 안 읽어서 꽤나 고생했던 문제다. 구슬을 일단 큐에 다 담고 터트려주는 방식을 택했는데 당연하게도 Python으로는 시간초과가 난다. PyPy로는 맞았는데, 다른 사람의 풀이를 보니 투포인터를 이용하여 구현한다면 Python으로도 충분히 돌아갈 것 같다.

 

그리고 중간에 인덱스 에러가 났는데 이는 큐가 비어있을 경우가 있기 때문이다. 임시 방편으로 if q: 로 q가 존재할 때만 코드를 실행하도록 했는데, for문을 돌때 새로운 로직을 이용해 개수를 세주는 식으로 고치는 게 나을 듯하다.

 

코드 수정하기는 다음 번에 하도록.... 그래도 이 문제를 풀면서 달팽이 행렬 마스터가 된 것 같다.

import sys
from copy import deepcopy
from collections import deque
input = sys.stdin.readline

# 좌 하 우 상
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]

blizard = [[-1, 0], [1, 0], [0, -1], [0, 1]]

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

# 구슬 없으면 0, 상어 0
grid = [list(map(int, input().split())) for _ in range(N)]

magic_shark = [(N+1)//2 - 1, (N+1)//2 - 1]

ans = 0
for _ in range(M):
    # 블리자드 마법 방향 d, 거리 s
    d, s = map(int, input().split())
    # 블리자드로 구슬 파괴
    y, x = magic_shark
    for i in range(s):
        dr, dc = blizard[d-1]
        ny, nx = y+dr, x+dc
        if 0 <= ny < N and 0 <= nx < N:
            grid[ny][nx] = 0
        y, x = ny, nx

    q = deque()
    turn = 0
    dire = 0
    cnt = 0
    move = 1
    y, x = magic_shark
    while True:
        if y == 0 and x == 0:
            break
        ny, nx = y + dy[dire], x + dx[dire]
        if grid[ny][nx]:
            q.append(grid[ny][nx])
        cnt += 1
        if cnt == move:
            dire = (dire + 1) % 4
            turn += 1
            cnt = 0
            if turn % 2 == 0:
                move += 1

        y, x = ny, nx

    # 큐 돌면서 구슬 폭발

    while True:
        if not q:
            break
        isFalse = True
        first_num = q[0]
        num = 1
        new_q = deque()
        for i in range(1, len(q)):
            if first_num != q[i]:
                if num >= 4:
                    ans += first_num * num
                    isFalse = False
                else:
                    for _ in range(num):
                        new_q.append(first_num)
                first_num = q[i]
                num = 1
            else:
                num += 1
        if num >= 4:
            ans += first_num * num
            isFalse = False
        else:
            for _ in range(num):
                new_q.append(first_num)
        q = deepcopy(new_q)
        if isFalse:
            break
    if q:
        new_q = deque()
        first_num = q[0]
        num = 1
        for i in range(1, len(q)):
            if first_num != q[i]:
                new_q.append(num)
                new_q.append(first_num)
                num = 1
                first_num = q[i]
            else:
                num += 1
        new_q.append(num)
        new_q.append(first_num)
        q = deepcopy(new_q)

    grid = [[0]*N for _ in range(N)]
    turn = 0
    dire = 0
    cnt = 0
    move = 1
    y, x = magic_shark
    for idx in range(len(q)):
        if not q:
            break
        if y == 0 and x == 0:
            break
        ny, nx = y + dy[dire], x + dx[dire]
        grid[ny][nx] = q[idx]
        cnt += 1
        if cnt == move:
            dire = (dire + 1) % 4
            turn += 1
            cnt = 0
            if turn % 2 == 0:
                move += 1

        y, x = ny, nx

print(ans)