[백준] 11559번 Puyo Puyo _ Python

[초기 접근 방법]

'애니팡' 같은 느낌의 문제

4개 이상이 인접한 구역이 있는지를 체크해서 폭탄을 터트린다.

이 때 일단 모든 맵에서 bfs()로 인접 지역을 체크하고

터트릴 폭탄이 있는 경우 터트리고 맵을 내려, 다시 인접한 구역이 있는지 확인한다.

 

 

[생각]

폭탄이 터트리고, 공백의 칸을 어떻게 내리는지 고민했던 문제

 

1) 일단 '.'으로 초기화하자

2) 그리고 각 플로우마다 맨 아랫줄부터 . 그리고 그 윗줄에 색깔이 있으면 교환하는 형식으로 내려오는 걸 구현하자

 

for i in range(11, -1, -1):
    for j in range(6):
        if board[i][j] != '.': # 아래에 빈 칸이 있는지 확인하고, 있으면 전부 내려버려
            for k in range(11, i, -1):
                if board[k][j] == '.':
                    board[i][j], board[k][j] = board[k][j], board[i][j]
                    break

 

 

[코드]

# 풀이 시간 : 52분
# 시간복잡도 : O(k * NlogE)
# 공간복잡도 : O(12*6)
# 참고 : -

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

# 일단 모든 좌표에 대한 visited[i][j] == True 가 될 때까지 그래프 탐색을 하면 된다.
    # 이 때 각 색깔별로 4개 이상이 연결되었을 시 "연쇄" 체크 (1개의 플로우로)

board = [list(map(str, input())) for _ in range(12)]

colors = ['R', 'G', 'B', 'P', 'Y']

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


def bfs(a, b, color):
    cnt = 1
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True

    bomb = [(a, b)]
    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 visited[nx][ny]:
                    cnt += 1
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    bomb.append((nx, ny))

    if cnt >= 4:
        for b in bomb:
            bombs.append(b)


fung = 0
while True:
    bombs = []
    visited = [[False] * 6 for _ in range(12)]
    for i in range(12):
        for j in range(6):
            # 색깔 보드 & 미방문 지역
            if board[i][j] != '.' and not visited[i][j]:
                bfs(i, j, board[i][j])

    if not bombs:
        break

    fung += 1
    for x, y in bombs:
        board[x][y] = '.'

    for i in range(11, -1, -1):
        for j in range(6):
            if board[i][j] != '.': # 아래에 빈 칸이 있는지 확인하고, 있으면 전부 내려버려
                for k in range(11, i, -1):
                    if board[k][j] == '.':
                        board[i][j], board[k][j] = board[k][j], board[i][j]
                        break

print(fung)