11559: Puyo Puyo

풀이 시간

• 22m

구현 방식

• 무난한 bfs 및 구현 문제였다

• 기억해두면 좋을 게, gravity 함수에서 row+1이 범위 내이고 아랫줄에 빈공간이 있을 때 현재줄과 아랫줄을 바꿔주고 그 외의 경우엔 바로 break를 해주는 방식이 구현 문제에서 많이 쓰이는 것 같다

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def bfs(x, y, color):
    queue = deque([]); queue.append((x, y))
    visit[x][y] = True
    puyo = [(x, y)]

    while queue:
        x, y = queue.popleft()
        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] == color and not visit[nx][ny]:
                    queue.append((nx, ny))
                    visit[nx][ny] = True
                    puyo.append((nx, ny))
    return puyo

def puyo_remove(puyos):
    for i in range(len(puyos)):
        for x, y in puyos[i]:
            board[x][y] = '.'

def gravity(board):
    for i in range(12-1, -1, -1):
        for j in range(6):
            if board[i][j] != '.':
                row = i
                while True:
                    if 0 <= row+1 < 12 and board[row+1][j] == '.':
                        tmp = board[row+1][j]
                        board[row+1][j] = board[row][j]
                        board[row][j] = tmp
                        row += 1
                    else:
                        break

board = []
for _ in range(12):
    board.append(list(sys.stdin.readline()[:-1]))

result = 0
while True:
    #터질 뿌요들 찾기
    visit = [[False]*6 for _ in range(12)]
    will_removed = []
    for i in range(12):
        for j in range(6):
            if board[i][j] != '.' and not visit[i][j]:
                tmp = bfs(i, j, board[i][j])
                if len(tmp) >= 4:
                    will_removed.append(tmp)

    #터질 뿌요가 없다면 종료
    if len(will_removed) == 0:
        break

    #뿌요 터트리기
    result += 1
    puyo_remove(will_removed)

    #중력
    gravity(board)

print(result)

결과