[백준][python]11559 Puyo Puyo

문제

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

소스코드

import sys
from collections import deque
if __name__ == "__main__":
    n,m = 12,6
    puyo = [list(input().rstrip()) for _ in range(n)]

    flag = True
    res = 0
    def bfs(i,j):
        q = deque()
        q.append([i,j])
        visited[i][j] = 1

        boom = [[i,j]]

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

        while q:
            x,y = q.popleft()
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if 0<=xx<n and 0<=yy<m and not visited[xx][yy]:
                    if puyo[x][y] == puyo[xx][yy]:
                        visited[xx][yy] = 1
                        q.append([xx,yy])
                        boom.append([xx,yy])
        if len(boom) >= 4:
            #제거하기
            for x,y in boom:
                puyo[x][y] = '.'
            #아래로 내리기
            for i in range(m):
                for j in range(n-1,-1,-1):
                    for k in range(j-1,-1,-1):
                        if puyo[j][i] == '.' and puyo[k][i] != '.':
                            puyo[j][i] = puyo[k][i]
                            puyo[k][i] = '.'
                            break
            return True
        return False


    while 1:
        flag = False
        visited = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if not visited[i][j] and puyo[i][j] != '.':
                    if bfs(i,j):
                        flag = True

        if flag:
            res +=1
        else:
            break
    print(res)

설명

1. 상하좌우 같은 뿌요가 있는지 체크해준다.
   1. 뿌요가 4개 이상이면 제거해준다
   2. 이때 뿌요 어떤 색상 하나만 터뜨리고 1연쇄 이렇게 하는게 아니고 현재 상태에서 되는 걸 모두 다 터트린다 한번에 여러개해도 1연쇄 라는 뜻
2. 4개 이상이라 제거될 뿌요가 있는지 확인한다.
   1. 있다면 제거해주고
   2. 아래로 내려준다
      1. 열을 기준으로 잡고
      2. 가장 밑에서 부터 확인해서 하나씩 내려준다
   3. 연쇄 + 1 처리 해준다.
3. 제거될 뿌요가 없다면 게임을 종료한다.