[코딩테스트][백준] 🔥 백준 21611번 "마법사 상어와 블리자드" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 60분

import sys
from collections import deque

input=sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]

tdx=[0,1,0,-1]
tdy=[-1,0,1,0]

n,m=map(int,input().split())

board=[list(map(int,input().split())) for _ in range(n)]

def blizard(board,d,s):
    global n
    x,y=n//2,n//2
    while s>0:
        nx=x+dx[d]
        ny=y+dy[d]
        board[nx][ny]=0
        x,y=nx,ny
        s-=1

def getMarbles(board):
    global n
    x,y,d=n//2,n//2,3
    visited=[[False]*n for _ in range(n)]
    visited[x][y]=True
    marbles=[]
    while True:
        td=(d+1)%4
        nx=x+tdx[td]
        ny=y+tdy[td]
        if nx<0 or ny<0 or nx>=n or ny>=n or visited[nx][ny]:
            nx=x+tdx[d]
            ny=y+tdy[d]
            if nx<0 or ny<0 or nx>=n or ny>=n or visited[nx][ny]:
                break
            x,y=nx,ny
            visited[nx][ny]=True
            if board[nx][ny]!=0:
                marbles.append(board[nx][ny])
            continue
        d=td
        x,y=nx,ny
        visited[nx][ny]=True
        if board[nx][ny]!=0:
            marbles.append(board[nx][ny])
    return marbles

def setMarbles(marbles):
    global n
    board=[[0]*n for _ in range(n)]
    x,y,d=n//2,n//2,3
    visited=[[False]*n for _ in range(n)]
    visited[x][y]=True
    marbles=deque(marbles)
    while True:
        td=(d+1)%4
        nx=x+tdx[td]
        ny=y+tdy[td]
        if nx<0 or ny<0 or nx>=n or ny>=n or visited[nx][ny]:
            nx=x+tdx[d]
            ny=y+tdy[d]
            if nx<0 or ny<0 or nx>=n or ny>=n or visited[nx][ny]:
                break
            x,y=nx,ny
            visited[nx][ny]=True
            if len(marbles)>0:
                board[nx][ny]=marbles.popleft()
            else:
                break
            continue
        d=td
        x,y=nx,ny
        visited[nx][ny]=True
        if len(marbles)>0:
                board[nx][ny]=marbles.popleft()
        else:
            break
    return board

def bombMarbles(marbles):
    global answer
    newMarbleList=[]
    stack=[]
    for i in range(len(marbles)):
        if len(stack)==0:
            stack.append(marbles[i])
        else:
            if stack[-1]==marbles[i]:
                stack.append(marbles[i])
            else:
                if len(stack)>=4:
                    answer+=stack[-1]*len(stack)
                    stack=[]
                else:
                    newMarbleList+=stack
                    stack=[]
                stack.append(marbles[i])
                    
    if len(stack)>=4:
        answer+=stack[-1]*len(stack)
    else:
        newMarbleList+=stack
    
    if newMarbleList==marbles:
        return False
    else:
        return newMarbleList

def changeMarble(marbles):
    newMarbleList=[]
    stack=[]
    for i in range(len(marbles)):
        if len(stack)==0:
            stack.append(marbles[i])
        else:
            if stack[-1]==marbles[i]:
                stack.append(marbles[i])
            else:
                newMarbleList.append(len(stack))
                newMarbleList.append(stack[-1])
                stack=[]
                stack.append(marbles[i])
    if len(stack)>0:
        newMarbleList.append(len(stack))
        newMarbleList.append(stack[-1])
    return newMarbleList
answer=0
for _ in range(m):
    d,s=map(int,input().split())
    blizard(board,d-1,s)
    marbles=getMarbles(board)
    while True:
        isChanged=bombMarbles(marbles)
        if not isChanged:
            break
        marbles=isChanged
    marbles=changeMarble(marbles)
    board=setMarbles(marbles)
print(answer)

마법사 상어의 블리자드: 구슬 폭파의 비밀! ❄️💥

첫 번째는 블리자드를 쓰는 방향으로 s개의 구슬을 제거하는 것이다. 이는 단순히 맵 위에서 방향에 맞게 없어지는 구슬 칸을 제거해주면 된다. 두 번째, 세번째는 구슬의 처리로 이루어진다. 그렇기 때문에 구슬을 따로 빼서 제거하면 편하게 풀이 할 수 있다.

각 방향을 벽이나 이미 방문한 칸이 있다면 전진으로 아니면 기본적으로 왼쪽으로 회전을 기준으로 나아간다. 그렇게 가운데에서부터 구슬을 전부 읽어온다. 빈 칸은 처리할 필요가 없기 때문에 1,2,3으로 이루어진 구슬만 가져온다. 이제 이 구슬을 폭파처리하면 된다. 구슬을 처음부터 읽어오면서 같으면 스택에 쌓고 다르면 지금까지 스택의 길이를 가지고 이를 처리한다. 4개 이상이면 스택을 비우고 현재 구슬을 스택에 넣어주며 4개 미만이면 스택을 결과물에 붙여주고 스택을 비우고 현재 구슬을 스택에 넣어준다. 이러한 과정을 터지는 구슬이 없을 때까지 반복한다. 이 때 터지는 구슬을 최종 정답에 반영해준다.

터지는 구슬이 이제 없다면 구슬을 변화시키면 되는데 이는 폭파와 비슷한 수순이다. 구슬을 읽어오면서 스택에 넣어서 같은 종류를 파악하고 다른 구슬이 나오면 터트리는 대신에 스택에 쌓인 구슬의 수와 종류를 결과물에 넣어준 후, 스택을 동일하게 처리하면 된다.

마법사 상어가 블리자드를 사용하였을 때 상황을 시뮬레이션한 문제이다. 하나의 큰 과정은 크게 4개로 나누어진다고 볼 수 있다.

첫 번째는 블리자드를 쓰는 방향으로 s개의 구슬을 제거하는 것이다. 이는 단순히 맵 위에서 방향에 맞게 없어지는 구슬 칸을 제거해주면 된다. 두 번째, 세번째는 구슬의 처리로 이루어진다. 그렇기 때문에 구슬을 따로 빼서 제거하면 편하게 풀이 할 수 있다.

각 방향을 벽이나 이미 방문한 칸이 있다면 전진으로 아니면 기본적으로 왼쪽으로 회전을 기준으로 나아간다. 그렇게 가운데에서부터 구슬을 전부 읽어온다. 빈 칸은 처리할 필요가 없기 때문에 1,2,3으로 이루어진 구슬만 가져온다. 이제 이 구슬을 폭파처리하면 된다. 구슬을 처음부터 읽어오면서 같으면 스택에 쌓고 다르면 지금까지 스택의 길이를 가지고 이를 처리한다. 4개 이상이면 스택을 비우고 현재 구슬을 스택에 넣어주며 4개 미만이면 스택을 결과물에 붙여주고 스택을 비우고 현재 구슬을 스택에 넣어준다. 이러한 과정을 터지는 구슬이 없을 때까지 반복한다. 이 때 터지는 구슬을 최종 정답에 반영해준다.

터지는 구슬이 이제 없다면 구슬을 변화시키면 되는데 이는 폭파와 비슷한 수순이다. 구슬을 읽어오면서 스택에 넣어서 같은 종류를 파악하고 다른 구슬이 나오면 터트리는 대신에 스택에 쌓인 구슬의 수와 종류를 결과물에 넣어준 후, 스택을 동일하게 처리하면 된다.

이렇게 Python으로 백준의 "마법사 상어와 블리자드" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊