[백준][구현] 마법사 상어와 블리자드

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

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

 

내가 작성한 코드

from collections import deque

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
roll = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def read_data():
    N, M = map(int, input().rstrip().split())
    board = []
    for _ in range(N):
        board.append(list(map(int, input().rstrip().split())))

    magic = deque()
    for _ in range(M):
        d, r = map(int, input().rstrip().split())
        magic.append((d-1, r))

    return N, M, board, magic

def destroy(d, r, board):
    x, y = N//2, N//2

    score = [0, 0, 0]
    for _ in range(r):
        x, y = x + dir[d][0], y + dir[d][1]
        score[board[x][y]-1] += 1
        board[x][y] = 0

    return tuple(score)

def in_range(x, y, N):
    return 0 <= x < N and 0 <= y < N

def make_q(n, N, board, x, y, q):
    if N < n:
        return

    q.append((x, y, board[x][y]))
    for _ in range(n - 2):
        x, y = x + roll[0][0], y + roll[0][1]
        q.append((x, y, board[x][y]))
    for d_x, d_y in roll[1:]:
        for _ in range(n - 1):
            x, y = x + d_x, y + d_y
            q.append((x, y, board[x][y]))

    x, y = x + roll[-1][0], y + roll[-1][1]
    make_q(n+2, N, board, x, y, q)


def move(N, board):
    x, y = (N//2)+roll[-1][0], (N//2)+roll[-1][1]
    q = deque()
    make_q(3, N, board, x, y, q)
    crnt = q.copy()

    while q:
        x, y, z = q.popleft()
        if board[x][y] != 0:
            nw_x, nw_y, nw_z = crnt.popleft()
            board[nw_x][nw_y] = z

    while crnt:
        nw_x, nw_y, z = crnt.popleft()
        board[nw_x][nw_y] = 0

def explosion(N, board):
    x, y = (N // 2) + roll[-1][0], (N // 2) + roll[-1][1]
    q = deque()
    make_q(3, N, board, x, y, q)
    crnt = q.copy()

    score = [0, 0, 0]
    v, cnt = board[x][y], 0
    coord = deque()
    while q:
        x, y, z = q.popleft()

        if v == z:
            cnt += 1
            coord.append((x, y, z))
        else:
            if cnt >= 4:
                score[v-1] += cnt
            else:
                while coord:
                    nw_x, nw_y, nw_z = coord.popleft()
                    crnt_x, crnt_y, crnt_z = crnt.popleft()
                    board[crnt_x][crnt_y] = nw_z

            v = z
            cnt = 1
            coord = deque([(x, y, z)])

    if v != 0 and cnt >= 4:
        score[v - 1] += cnt
    else:
        while coord:
            nw_x, nw_y, nw_z = coord.popleft()
            crnt_x, crnt_y, crnt_z = crnt.popleft()
            board[crnt_x][crnt_y] = nw_z

    while crnt:
        nw_x, nw_y, nw_z = crnt.popleft()
        board[nw_x][nw_y] = 0

    return tuple(score)

def change(N, board):
    x, y = (N // 2) + roll[-1][0], (N // 2) + roll[-1][1]
    q = deque()
    make_q(3, N, board, x, y, q)
    crnt = q.copy()

    v, cnt = board[x][y], 0
    while q:
        x, y, z = q.popleft()

        if v == z:
            cnt += 1
        else:
            for i in range(2):
                if not crnt:
                    break
                crnt_x, crnt_y, crnt_z = crnt.popleft()
                board[crnt_x][crnt_y] = cnt if i % 2 == 0 else v
            if not crnt:
                break

            v = z
            cnt = 1

def get_answer(N, M, board, magic):
    x, y, z = 0, 0, 0
    while magic:
        d, r = magic.popleft()
        a, b, c = destroy(d, r, board)
        # x, y, z = x+a, y+b, z+c
        move(N, board)
        a, b, c = explosion(N, board)
        while not(a==b==c==0):
            x, y, z = x + a, y + b, z + c
            a, b, c = explosion(N, board)
        change(N, board)

    return x + (y * 2) + (z * 3)

N, M, board, magic = read_data()
print(get_answer(N, M, board, magic))
# for z in board:
#     print(z)
# print()

• Queue
  
  • 구슬 탐색 순서를 N기준 재귀로 정의
  • 재귀로 좌표와 값을 Queue에 삽입
  • Queue를 복사하여, 하나는 현재 탐색용, 다른 하나는 삽입할 위치로 사용

 

다른 사람이 작성한 코드

None

• 강한 구현 문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 착각한 조건
  
  • 마법을 사용한 구슬도 카운팅 -> 폭발로 인한 구슬만 카운팅해야함
  • 구슬 변화 A, B에서 3개인 구슬은 A, B, A를 삽입 -> 구슬 개수에 무관하게 A, B만 삽입