[백준 11559] Puyo Puyo (Python)

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

문제풀이

 

BFS를 이용한 구현문제이다. 주어진 조건만 잘 구현하면 쉽게 해결할 수 있다.

 

1. 뿌요 탐색 및 뿌요 부수기

- 현재 위치에서 동일한 색상의 뿌요가 4개 이상일 경우 뿌요를 부신다.

 

2. 1의 과정에서 없앤 뿌요가 있으면 뿌요를 내려준다.

- 없앤 뿌요가 없으면 더 이상 진행할 것이 없으므로 결과를 바로 출력한다.

 

코드 보면 쉽게(?) 이해할 수 있다.

 

코드

import sys
from collections import deque

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

# BFS 를 통해 뿌실 뿌요 탐색
def bfs(x, y, color):
    global flag
    tmp_q = deque([(x, y)])
    l = deque([(x, y)])
    check = [[False] * 6 for _ in range(12)]
    check[x][y] = True
    while tmp_q:
        x, y = tmp_q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < 12 and 0 <= ny < 6:
                if board[nx][ny] == color and not check[nx][ny]:
                    check[nx][ny] = True
                    tmp_q.append((nx, ny))
                    l.append((nx, ny))
    # 동일 색의 뿌요가 4개 이상 붙어있을 경우 뿌요 부수기
    if len(l) >= 4:
        while l:
            x, y = l.popleft()
            board[x][y] = '.'
        flag = True

# 뿌요를 부신 후 남아있는 뿌요 내리기
def move_down():
    i, j = 11, 5
    while j >= 0:
        cnt = 0
        while i >= 0:
            if board[i][j] == '.':
                cnt += 1
                i -= 1
                continue
            if not cnt:
                i -= 1
                continue
            board[i + cnt][j] = board[i][j]
            board[i][j] = '.'
            i += cnt
            cnt = 0
        j -= 1
        i = 11

if __name__ == '__main__':
    board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(12)]
    q = deque()
    ans = 0
    for i in range(12):
        for j in range(6):
            if board[i][j] == '.': continue
            q.append((i, j))
    while q:
        size = len(q)
        flag = False # 없앤 뿌요가 있는지 여부 체크
        for _ in range(size):
            x, y = q.popleft()
            # 이미 부신 뿌요는 탐색하지 않음
            if board[x][y] == '.': continue
            color = board[x][y]
            # 뿌요 탐색 및 부수기
            bfs(x, y, color)
        # 뿌요를 부셨다면 1 증가
        if flag: ans += 1
        # 부실 뿌요가 없다면 종료
        else:
            print(ans)
            exit(0)
        # 뿌요 내리기
        move_down()
        for i in range(12):
            for j in range(6):
                if board[i][j] == '.': continue
                q.append((i, j))
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!