[백준] 11559 Puyo Puyo (Python/파이썬)

<문제 링크>

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

11559번: Puyo Puyo

<풀이 전략>

1. 구현문제이다.

2. 구현해야 할 요소는 '블럭이 터지는 부분' + '블럭이 터지고 내려오는 부분' 2가지이다.

3. 블럭이 터지는 부분은 bfs를 이용하여 구현했다.

4. 블럭이 터지고 내려오는 부분은 슬라이싱을 이용해 행 단위에서 코드를 작성하기 위해 배열을 회전 시켜서 했다.

 

<정답 코드>

from collections import deque
import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220920 11559 Puyo Puyo

# 정답코드

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]


# bfs로 뿌요 터트리는 함수
def bfs(r, c, puyo):
    # 방문 여부 표시
    visited[r][c] = 1

    # 인접 뿌요 세주기 및 뿌요의 좌표 저장
    cnt = 1
    temp = [(r, c)]

    queue = deque()
    queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < 12 and 0 <= nc < 6:
                # 같은 뿌요이며 미방문일 경우
                if board[nr][nc] == puyo and visited[nr][nc] == 0:
                    # 방문 여부 표시
                    visited[nr][nc] = 1

                    # 뿌요 세주기 및 좌표 저장
                    cnt += 1
                    temp.append((nr, nc))

                    queue.append((nr, nc))

    # 인접한 뿌요가 4개 이상일 경우
    if cnt >= 4:
        # 저장된 좌표의 뿌요들을 '.'으로 바꿔준다.
        for r, c in temp:
            board[r][c] = '.'
        # True 반환
        return True

    # 뿌요가 터지지 않았으면 False 반환
    return False


# 뿌요가 터진 후 뿌요가 중력의 영향을 받아 내려오는 함수
def clear_board(board):
    # 행에서 작업하기 위해 배열을 반시계방향으로 90도 시켜준다.
    rotate_board = list(map(list, zip(*board[::])))[::-1]
    
    for row in rotate_board:
        # start: 처음 뿌요가 등장하는 인덱스 위치 (-1로 초기화)
        start = -1
        for i in range(12):
            # 첫 뿌요 인덱스 저장
            if row[i] != '.':
                start = i
                break
        
        # 해당 행에 뿌요가 있을 경우
        if start != -1:
            # 빈 공간을 빼주고 앞에 빈 공간을 채워준다.
            for j in range(start, 12):
                if row[j] == '.':
                    row.pop(j)
                    row.insert(0, '.')
    
    # 다시 원래 방향으로 된 배열(시계방향 90도 회전) 반환
    return list(map(list, zip(*rotate_board[::-1])))


# ans: 연쇄 회수
ans = 0
# board: 뿌요가 놓인 배열
board = [list(map(str, input())) for _ in range(12)]


while True:
    # flag 해당 시행에서 연쇄가 있었는지 나타내는 변수
    flag = False
    # visited: 방문여부 표시 배열
    visited = [[0 for _ in range(6)] for _ in range(12)]

    # 배열에 뿌요가 있을 경우 탐색 실시
    for r in range(12):
        for c in range(6):
            if board[r][c] != '.':
                # 연쇄가 있었을 경우 flag == True
                if bfs(r, c, board[r][c]):
                    flag = True

    # 해당 시행에서 연쇄가 있었을 경우
    if flag:
        # 연쇄 회수를 세주고 뿌요의 상태를 정리해주고 다음 회차로 넘어간다.
        ans += 1
        board = clear_board(board)

    # 시행이 없었을 경우 게임을 종료한다.
    else:
        break

# 연쇄 회수 출력
print(ans)