[백준] 11559번: Puyo Puyo - Python풀이 (BFS, 구현)

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

11559번: Puyo Puyo

카카오의 프렌즈 4 블록 문제랑 매우 유사한 시뮬레이션 + bfs문제였다 

4블록이랑 다른 점은 4블록은 정사각형을 만들어야 없어지고 Puyo Puyo는 연속해서 4개 블록연결되어 있으면 어떤모양이든 터진다 ! 

블록이 터진 후에 위에서부터 아래로 빈칸이 없도록 블록을 내려주는것도 유사하다 

import sys
from collections import deque
board = []
input = sys.stdin.readline
for i in range(12):
    data = input()
    temp = []
    for j in data:
        temp.append(j)
    board.append(temp)

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

def block_down():
    while True:
        flag = False
        for i in range(11):
            for j in range(6):
                if board[i][j] != '.' and board[i + 1][j] == '.':
                    board[i + 1][j] = board[i][j]
                    board[i][j] = '.'
                    flag = True
        if not flag:
            break

def bfs(x, y, cnt, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    flag = False # 연쇄 발생 여부
    erase_block = set()
    erase_block.add((x, y))
    while queue:
        x, y = queue.popleft()
        puyo = board[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 12 and 0 <= ny < 6:
                if board[nx][ny] == puyo and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    cnt += 1
                    erase_block.add((nx, ny))
    if cnt >= 4:
        flag = True
        for r, c in erase_block:
            board[r][c] = '.'

    return flag

count = 0
while True:
    visited = [[False] * 6 for _ in range(12)]
    flag = False
    for i in range(12):
        for j in range(6):
            if board[i][j] != '.' and not visited[i][j]:
                if bfs(i, j, 1, visited):
                    flag = True
    if not flag: # 연쇄 없음
        break
    else:
        count += 1 # 연쇄 발생
    block_down()

print(count)