파이썬 | 백준 | 11559 | Puyo Puyo

solution

1. 4개 이상 연결되어있는 경우 찾기

2. 4개 이상 연결된 뿌요의 좌표를 boom 배열에 저장해 한 번에 터트림

3. 4개 이상의 연결된 뿌요가 없을 때까지 1,2 반복

# 11559, Puyo Puyo
import sys
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y, ch):
    visited[x][y] = 1
    q = deque()
    tmp = []    # 좌표 임시 저장하는 배열
    q.append((x, y))
    tmp.append((x, y))

    while q:
        a, b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < 12 and 0 <= ny < 6:
                if game[nx][ny] == ch and visited[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = 1
                    tmp.append((nx, ny))
    # 4개가 넘으면 한 번에 터트리는 boom 배열에 extend함
    if len(tmp) >= 4:
        boom.extend(tmp)


def chk():
    for i in range(12):
        for j in range(6):
            if game[i][j] != '.' and visited[i][j] == 0:
                bfs(i, j, game[i][j])


# 터트림
def rm(x):
    for i in range(x[0], 0, -1):
        game[i][x[1]] = game[i-1][x[1]]
    game[0][x[1]] = '.'


game = [list(sys.stdin.readline().rstrip()) for _ in range(12)]
cnt = 0
while True:
    visited = [[0] * 6 for _ in range(12)]
    boom = []
    chk()
    # 같은 열일 경우, 위에 있는 행부터 터트려야 함. 행이 10, 11일 때 10행, 11행 순서로 터져야 제대로 삭제됨
    # while문에서 pop으로 뒤에 있는 원소부터 rm 함수를 호출해 삭제하므로
    # 내림차순 정렬 필요
    boom.sort(key=lambda x: -x[0])
    # 터트릴 boom 배열이 비어있으면 4개 이상 모여있는 경우가 없는 것
    if len(boom) == 0:
        break
    # boom배열에 있는 좌표 이용해서 터트림
    while boom:
        rm(boom.pop())
    cnt += 1
print(cnt)

 

문제 출처 www.acmicpc.net/problem/11559

11559번: Puyo Puyo