🥇 11559 Puyo Puyo
문제
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
입력
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.
출력
현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.
예제
- input
......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.- output
3분석
기존의 뿌요뿌요 게임을 구현하는 문제이다. 중점을 포함한 주변에 4개 이상의 같은 색상의 뿌요가 있다면 터져서 사라지고 연쇄 1 추가된다. 이 때 동시에 다른 색상도 터지게 되면 2가 아닌 1만 추가된다는 점을 유의해야 한다.
중점 주변을 탐색하는 것은 bfs로 찾고, 터진 경우는 True, 아닌 경우는 False로 리턴해준다.
모든 곳을 탐색 완료했을 때, 만약 한 번도 터지지 않았을 경우엔 while loop를 종료 시키고 답을 출력한다. 한 번이라도 터졌을 때에는 연쇄를 하나 추가시키고 빈 자리에 뿌요를 내린다.
뿌요를 내릴 때엔 아래부터 검사해서 값을 이동시켜주면 된다.
소스 코드
import sys
from collections import deque
input = sys.stdin.readline
def down():
# board에서 뿌요가 삭제된 빈 공간을 위에 있는 뿌요를 내려서 채움
for i in range(10, -1, -1):
for j in range(6):
for k in range(11, i, -1):
# j행에는 뿌요가 있고 k행에는 빈공간이면 교환
if board[i][j] != '.' and board[k][j] == '.':
board[k][j] = board[i][j]
board[i][j] = '.'
break
def bfs(x, y, color):
visited = [[False for _ in range(6)] for _ in range(12)]
visited[x][y] = True
q = deque([[x, y]])
puyo = [(x, y)] # (x, y)포함해서 같은 색의 뿌요가 4개 이상있어야 사라짐
pang = False # 연쇄가 일어났는지 아닌지 확인하는 변수
while q:
x, y = q.popleft()
for nx, ny in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
if nx < 0 or ny < 0 or nx >= 12 or ny >= 6:
continue
# 같은 색상일 때만 선택
if not visited[nx][ny] and board[nx][ny] == color:
visited[nx][ny] = True
q.append([nx, ny])
puyo.append((nx, ny))
# (x, y)를 포함해 4개 이상이 모였다면 터진다.
if 4 <= len(puyo):
pang = True # 연쇄 발생
# 방문 처리된 뿌요들을 없앰
for x, y in puyo:
board[x][y] = '.'
return pang
board = []
for _ in range(12):
board.append(list(input().strip()))
streak = 0 # 연쇄
while True:
cnt = 0
for i in range(12):
for j in range(6):
if board[i][j] != '.':
cnt += bfs(i, j, board[i][j])
if cnt == 0: # 더 이상 터지지 않을 경우 break
print(streak)
break
else: # 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가
streak += 1
down() # 터진 자리에 뿌요를 내린다