문제 링크
https://www.acmicpc.net/problem/21609
🕒 Python 풀이시간: 55분
from collections import deque
import sys
dx=[0,0,-1,1]
dy=[-1,1,0,0]
INF=1e9
input=sys.stdin.readline
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
def findBlockGroup(x,y):
q=deque()
q.append((x,y))
color=board[x][y]
visited=[[False]*n for _ in range(n)]
visited[x][y]=True
groupBlocks=[(x,y,color)]
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if visited[nx][ny]:
continue
if board[nx][ny]==-1 or board[nx][ny]==INF:
continue
if board[nx][ny]==0 or board[nx][ny]==color:
q.append((nx,ny))
visited[nx][ny]=True
groupBlocks.append((nx,ny,board[nx][ny]))
return groupBlocks
def setBlockGroup(groupBlocks):
size=len(groupBlocks)
groupBlocks.sort()
rainbowBlockNum=0
standardBlock=False
for x,y,c in groupBlocks:
if c==0:
rainbowBlockNum+=1
elif not standardBlock:
standardBlock=(x,y,c)
return [size,rainbowBlockNum,standardBlock,groupBlocks]
def turnBoard(board):
newBoard=[[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
newBoard[n-1-j][i]=board[i][j]
return newBoard
def gravity(board):
for j in range(n):
arr=[]
for i in range(n):
arr.append(board[i][j])
result=[]
mid=deque()
k=0
while True:
if k>=n:
result+=mid
break
elif arr[k]!=INF and arr[k]!=-1:
mid.append(arr[k])
k+=1
elif arr[k]==INF:
mid.appendleft(arr[k])
k+=1
elif arr[k]==-1:
mid.append(arr[k])
result+=mid
mid=deque()
k+=1
for i in range(n):
board[i][j]=result[i]
return board
score=0
while True:
blockGroups=[]
for i in range(n):
for j in range(n):
if board[i][j]>0 and board[i][j]!=INF:
blockGroup=findBlockGroup(i,j)
if len(blockGroup)>=2:
blockGroups.append(setBlockGroup(blockGroup))
if len(blockGroups)==0:
break
blockGroups.sort(key=lambda x:(-x[0],-x[1],-x[2][0],-x[2][1]))
selectedBlockGroup=blockGroups[0]
score+=pow(selectedBlockGroup[0],2)
for x,y,c in selectedBlockGroup[3]:
board[x][y]=INF
board=gravity(board)
board=turnBoard(board)
board=gravity(board)
print(score)🐟 상어 중학교의 블록 대소동!
상어 중학교의 코딩 동아리에서 만든 게임에 관련된 시뮬레이션 문제이다. 각 모든 칸에는 처음에 블록이 있고 이 블록은 1~M 중의 색을 가지고 있는 일반 블록과 0인 무지개 블록 -1인 검은 블록으로 이루어져 있다. 이 때, 블록 그룹을 파악하여 이에 대한 처리를 수행하는 문제이다.
블록 그룹은 반드시 일반 블록을 한개 이상 가지고 있어야 하며 검은 블록을 포함하지 않고 무지개 블록의 갯수는 상관 없다. 즉, 블록 그룹이 중복되게 무지개 블록을 보유하고 있어도 된다는 뜻이다. 그렇기 때문에 BFS를 블록 하나의 수준에 수행하면서 visited는 한 번의 BFS가 수행될 때 새로 초기화 시켜주어야 한다. 또한 블록 그룹은 동일한 일반블록 색상만 포함할 수 있기 때문에 이것도 조건으로 걸어주어야 한다. 마지막으로 후에 제거될 빈칸도 그룹에 포함될 수 없기 때문에 제외시켜 주면서 찾아야 한다.
이렇게 모든 블록 그룹을 블록의 리스트 형태로 찾아놓는다면 이것이 2개 이상일 때만 블록 그룹으로 취급될 수 있다. 이 찾은 블록 그룹 중에 우리는 기준에 따라 블록 그룹을 하나만 선정해야 하므로 그 것을 처리해준다. 여기서는 setBlockGroup으로 처리해 주었다. 여기서는 리스트의 크기, 무지개 블록의 수, 기준 블록 등을 찾아서 넣어준다. 이 것을 문제의 1번 조건에 따라 정렬해 주면 맨 앞에 있는 블록 그룹이 우리가 지울 블록 그룹이 된다.
이 블록 그룹을 INF로 지워진 처리를 한다. 그런 후, 이 것만큼의 점수를 획득한다. 마지막으로는 중력->회전-> 중력 처리를 해주어야 하는데 이 때, 배열의 회전은 간단히 좌표를 통해 수행하면 된다. 중요한 것은 중력, 즉, 밑으로 블록들을 내리되 -1에서는 걸리게 해야한다는 것이다. 이것을 위하여 배열의 한 행을 탐색하면서 일반 블록이라면 계속해서 이어붙인다. 만약 빈칸이라면 그 칸은 상황상 지나쳐 내려가고 일반 블록이 뒤에 오기 때문에 빈칸을 만난다면 앞에다가 붙인다. -1, 즉, 검은 블록을 만난다면 중력이 작용하지 않고 쌓이기 때문에 지금까지의 결과를 우리가 구하는 최종 행 세팅에 이어 붙여준다. 그런 후 새롭게 구하면 된다. 마지막으로 끝까지 행 작업이 끝난다면, 바닥에 도달했다면 세팅해오던 블록들을 결과에 이어붙여주면 된다.
이렇게 Python로 백준의 "상어 중학교" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
