백준 11559 Puyo Puyo

과정

• BFS, 구현
• 같은 색 확인 할 BFS 함수
• 터지면 밑으로 내려올 함수
• 내려온 상태에서 더 이상 터지지 않으면 횟수 세지 않기

from collections import deque

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

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

bfs_res = 0


def bfs(x, y, visited, origin_color):
    global bfs_res
    queue = deque([(x, y)])
    same_color = []
    while queue:
        a = queue.popleft()
        x = a[0]
        y = a[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 6 or ny < 0 or ny >= 12 or visited[ny][nx]:
                continue
            if map_lst[ny][nx] == origin_color:
                visited[ny][nx] = True
                same_color.append((nx, ny))
                queue.append((nx, ny))

    if len(same_color) >= 4:
        bfs_res += 1
        for same in same_color:
            map_lst[same[1]][same[0]] = "."
    return visited


# 위에서 채워서 내려오기
def down(down_res=0):
    for i in range(6):
        down_cnt = 0
        while True:
            for j in range(10, -1, -1):
                if map_lst[j + 1][i] == "." and map_lst[j][i] != ".":
                    map_lst[j + 1][i] = map_lst[j][i]
                    map_lst[j][i] = "."
                    down_cnt += 1
                    down_res += 1
            if down_cnt > 0:
                down_cnt = 0
            else:
                break
    return down_res


ans = 0
while True:
    visited = [[False for _ in range(6)] for _ in range(12)]
    bfs_res = 0
    for i in range(6):
        for j in range(12):
            if map_lst[j][i] != "." and not visited[j][i]:
                visited = bfs(i, j, visited, map_lst[j][i])
    if bfs_res != 0:
        ans += 1
    res = down()
    if res == 0:
        break

print(ans)

• 반례 - 답은 2

  ....Y.
  ....R.
  ....Y.
  ....R.
  ....R.
  ....Y.
  ....Y.
  ....Y.
  ....RR
  ...YRR
  ..GGYY
  ..GGYY