11559 - Puyo Puyo
문제
뿌요뿌요의 룰은 다음과 같다.
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!
코드
from collections import deque
def bfs(i, j, total):
q = deque()
q.append((i, j))
count = 1
visited = [[False] * 6 for _ in range(12)]
visited[i][j] = True
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < 12 and 0 <= ny < 6 and puyo[x][y] == puyo[nx][ny] and not visited[nx][ny]:
count += 1
q.append((nx, ny))
visited[nx][ny] = True
if count >= 4:
total += 1
for i in range(12):
for j in range(6):
if visited[i][j]:
puyo[i][j] = '.'
return total
def rearrange():
for i in range(10, -1, -1):
for j in range(6):
if puyo[i][j] != '.' and puyo[i+1][j] == '.':
idx = i+1
while idx < 12:
if idx == 11 and puyo[idx][j] == '.':
puyo[i][j], puyo[idx][j] = puyo[idx][j], puyo[i][j]
elif puyo[idx][j] != '.':
puyo[i][j], puyo[idx-1][j] = puyo[idx-1][j], puyo[i][j]
break
idx += 1
puyo = [list(input()) for _ in range(12)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = 0
while True:
total = 0
for i in range(12):
for j in range(6):
if puyo[i][j] != '.':
total = bfs(i, j, total)
if total == 0:
break
else:
result += 1
rearrange()
print(result)한마디
BFS를 이용해 같은 색상이 4개 이상 모이면 해당 색상 값을 없앴다. 그 후 rearrange 함수를 통해 필드 내 뿌요들을 전부 아래로 떨어뜨렸다.
