[Python] 백준 11559 - Puyo Puyo [Gold4]

뿌요뿌요라는 게임을 들어보았을지 모르겠지만, 뿌요뿌요는 그림으로 봐도 알 수 있듯이 일본의 SEGA사에서 만든 게임이고 테트리스 처럼 여러 색깔과 모양의 블럭들이 내려와서 바닥이나 제일 위에 있는 블럭과 맞닿았을 때 그 상태에서 상하좌우로 4개의 같은 색깔의 모양이 위치하게 되면 그 블럭들이 터지면서 점수가 오르는 게임이다. 블럭이 터지게 되면 위에 있는 블럭들이 아래의 빈 공간을 메꾸기 위해 내려오게 되고 그 과정에서 새롭게 4개의 블럭이 생기면 연쇄적으로 터질 수 있다.

따라서 이 문제에서도 이 게임의 방식과 동일하게 구현을 하면 된다.

출처

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

풀이

BFS를 이용하는데, 블럭이 모여서 터지게 되면 중력의 영향을 받아서 터진 블럭 위에 있는 블럭들이 내려와야 하기 때문에 이 부분에 대한 함수도 구현을 하였다.

BFS의 경우 다른 문제들을 풀 때처럼 Map과 Visited를 선언해서 범위 내부를 탐색하면서 count를 세주다가 4보다 크거나 같아지면 (같은 색깔의 블럭이 4개 이상 연결되어 있는 경우) 터뜨린 블럭의 위치에 '.'로 대체해서 터뜨렸다는 것을 표시해준다.

gravity 함수의 경우 3중 for문을 돈다. 첫번째 가장 바깥쪽 for문은 열들을 돌면서 탐색을 하고 두번째 for문은 아래부터 위를 탐색하면서 빈칸을 찾아서 블럭을 내리는 역할이기 때문에 역방향 탐색을 하고 마지막 세번째 for문은 두번째 for문을 도는 과정에서 빈칸을 찾으면 그 위에 있는 블록을 아래로 내리는 역할을 하게 된다.

solve 함수는 flag 변수를 이용해서 블럭들을 계속 터뜨려주다가 더 이상 연쇄적으로 터질 블럭들이 없는 경우 반복문을 탈출하면서 연쇄적으로 터진 횟수를 return하게 하였다.

 

소스 코드

import sys
input = sys.stdin.readline

Map = [list(input().rstrip()) for _ in range(12)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q = [(x, y)]
    visited = [[0]*6 for _ in range(12)]
    visited[x][y] = 1
    cnt = 1
    color = Map[x][y]
    while q:
        x, y = q.pop(0)
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < 12 and 0 <= ny < 6 and not visited[nx][ny] and Map[nx][ny] == color:
                visited[nx][ny] = 1
                cnt += 1
                q.append((nx, ny))
    if cnt >= 4: # 4개 이상의 블록이 연결되어 있으면
        for i in range(12):
            for j in range(6):
                if visited[i][j]:
                    Map[i][j] = '.' # 터뜨릴 블록을 .으로 바꿈
        return True
    return False

def gravity():
    for j in range(6):
        for i in range(11, -1, -1): # 아래에서부터 위로 올라가면서 빈칸을 찾아서 블록을 내림
            if Map[i][j] == '.': # 빈칸을 찾으면
                for k in range(i-1, -1, -1): # 그 위에 있는 블록을 찾아서 내림
                    if Map[k][j] != '.':
                        Map[i][j], Map[k][j] = Map[k][j], Map[i][j] # 블록을 내림
                        break
                    
def solve():
    cnt = 0
    while True:
        flag = False
        for i in range(12):
            for j in range(6):
                if Map[i][j] != '.':
                    if bfs(i, j): # 4개 이상의 블록이 연결되어 있으면
                        flag = True
        if not flag:
            break
        gravity() 
        cnt += 1
    return cnt

print(solve())

결과