백준 11559 Puyo Puyo (파이썬)

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

11559번: Puyo Puyo

1. 부술 수 있는 뿌요를 bfs로 구하여 모두 부순다. 이 때 더 이상 부술 수 없으면 연쇄한 횟수를 출력

   뿌요를 부순 횟수에 관계없이 부수는 과정이 발생하면 연쇄는 무조건 한 번 증가한다

2. 부순 후 떨어질 수 있는 뿌요를 구한다

   뿌요의 바로 아래에 . 이 있으면 떨어져야 하므로 다른 뿌요가 있거나 바닥에 닿을 때 까지 뿌요를 떨어뜨린다.

3. 다시 1번부터 과정을 반복

from collections import deque
import sys

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

def bfs(x, y, flag):
    q = deque()
    c = [[0]*6 for _ in range(12)]
    q.append([x, y])
    cnt = 1
    c[x][y] = cnt
    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:
                if a[nx][ny] == a[x][y] and c[nx][ny] == 0:
                    cnt += 1
                    c[nx][ny] = 1
                    q.append([nx, ny])

    if cnt >= 4:
        flag += 1
        for i in range(12):
            for j in range(6):
                if c[i][j] == 1:
                    a[i][j] = '.'
    return flag

def check_fall():
    for i in range(10, -1, -1):
        for j in range(6):
            if a[i][j] != '.' and a[i+1][j] == '.':
                for k in range(i+1, 12):
                    if k == 11 and a[k][j] == '.':
                        a[k][j] = a[i][j]
                    elif a[k][j] != '.':
                        a[k-1][j] = a[i][j]
                        break
                a[i][j] = '.'

a = [list(map(str, input().strip())) for _ in range(12)]

ans = 0
while True:
    cnt = 0
    for i in range(12):
        for j in range(6):
            if a[i][j] != '.':
                cnt = bfs(i, j, cnt)
    if cnt == 0:
        print(ans)
        break
    else:
        ans += 1
    check_fall()