[python] 백준 11559 Puyo Puyo

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

11559번: Puyo Puyo

 

문제 해결

• 문제 상황을 시물레이션으로 구현할 수 있으면 어렵지 않은 문제
• 첫 행 첫 열부터 하나씩 확인을 해서 이어져 있는 같은 색 뿌요가 4개 이상인지 BFS를 이용해 확인한다.
• 확인한 점은 다시 확인할 필요가 없으므로 visited를 이용해 구별해서 방문 한 지점은 패스한다.
• 이어져 있는 같은색 점이 4개 이상이면 터뜨리면서 빈 공간으로 만든다.
• 모두 한바퀴 확인하면 그 다음 중력으로 인해 밑으로 떨어지는 알고리즘을 만든다. 이는 마지막 행부터 바로 위 행까지 비교를 해가며 특정 지역 행의 y열이 빈 공간이고 그 위에 행의 y열이 뿌요가 있을 때 스위치를 함으로써 뿌요를 아래로 떨어뜨리는 알고리즘을 짤 수 있다.

 

CODE

import sys
from collections import deque
input = sys.stdin.readline

def down():
    for i in range(6):
        for j in range(10,-1,-1):
            for k in range(11,j,-1):
                if board[j][i] != "." and board[k][i] ==".":
                    board[k][i] = board[j][i]
                    board[j][i] = "."
                    break

def bfs(x,y):
    que = deque()
    que.append((x,y))
    temp.append((x,y))
    while que:
        a, b = que.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0<=nx<12 and 0<=ny<6 and board[nx][ny] == board[x][y] and visited[nx][ny] ==0:
                que.append((nx,ny))
                temp.append((nx,ny))
                visited[nx][ny] = 1
                
def delete(temp):
    for a, b in temp:
        board[a][b] = "."


if __name__=='__main__':
    board = [list(input().strip()) for _ in range(12)]
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    answer = 0
    while 1:
        flag = 0
        visited =[[0 for _ in range(6)] for _ in range(12)]
        for i in range(12):
            for j in range(6):
                if board[i][j] != '.' and not visited[i][j]:
                    visited[i][j] = 1
                    temp = []
                    bfs(i,j)
                    if len(temp) >= 4:
                        flag = 1
                        delete(temp)
        if flag ==0:
            break
        down()
        answer += 1
    print(answer)