백준 11559 Puyo Puyo

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

g = [list(input()) for _ in range(12)]

def dfs(i, j, check, bomb):
    q = deque()
    same = []
    q.append((i, j))
    check[i][j] = 0
    while q:
        x, y = q.popleft()
        same.append((x, y))
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if nx < 0 or ny < 0 or nx >= 12 or ny >= 6:
                continue
            if check[nx][ny] == -1 and g[nx][ny] == g[i][j]:
                check[nx][ny] = 0
                q.append((nx, ny))
    if len(same) >= 4:
        return bomb + same
    return bomb

def drop(g, line, start):
    if start == -1 or start == 11:
        return 
    if g[start][line] != '.' and g[start + 1][line] == '.':
        g[start + 1][line], g[start][line] = g[start][line], g[start + 1][line]
        drop(g, line, start+1)
    else:
        drop(g, line, start-1) 
    
cnt = 0
while True:
    check = [[-1] * 6 for _ in range(12)]
    bomb = []
    for i in range(11, -1, -1):
        for j in range(6):
            if check[i][j] == -1 and g[i][j] != '.':
                bomb = dfs(i, j, check, bomb)
    if not bomb:
        break
    cnt += 1
    for i, j in bomb:
        g[i][j] = '.'
    for line in range(6):
        for start in range(10, -1, -1):
            drop(g, line, start)
    
print(cnt)

1 연쇄는
1. 터트리는 연산 : bfs로 같은 알파벳 다 찾음 -> 4개 이상이면 터트림 -> 터트릴거 없으면 종료됨
2. 중력에 의해 내려가는 연산 : 재귀로 내릴 수 있을 때까지 내린다