[백준-파이썬] 11559: Puyo Puyo

문제 보러 가기

문제에 나와있는 뿌요 뿌요 룰을 그대로 구현하면 된다.

1. 쭉 보면서 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있는지 보고
2. 그런 그룹이 있으면, 뿌요들 터지게 하기 (단, 여러 그룹이 터져도 한 번의 연쇄만 추가됨)
3. 남은 뿌요들이 중력의 영향을 받아서 떨어지게 하기
4. 또 다시 1번으로 돌아가기

같은 색 뿌요가 상하좌우 4개 이상 연결되어 있는지 보는 것은 BFS로 했다.
중력의 영향받아서 잘 떨어지게 하는 것을 구현하는 게 어려웠다.ㅠ if와 while들을 이용해서 구현했다. 좀 복잡한 시뮬레이션, 구현도 연습해야겠다.
전에 풀었던 10703: 유성 문제가 떠올라서 비슷하게 하려고 했으나, 다른 점이 많아서 참고만 한 것 같다.

import collections
import sys

input = sys.stdin.readline


# 그 위치부터 봐서 같은 색 뿌요 개수 세기
def bfs(i, j, type):
    visited = [[False] * 6 for _ in range(12)]
    cnt = 1
    q = collections.deque()
    q.append((i, j))
    visited[i][j] = True
    while q:
        ii, jj = q.popleft()
        for k in range(4):
            ni = ii + directions[k][0]
            nj = jj + directions[k][1]
            if 0 <= ni < 12 and 0 <= nj < 6 and visited[ni][nj] == False and arr[ni][nj] == type:
                cnt += 1
                q.append((ni, nj))
                visited[ni][nj] = True
    return cnt


# 터뜨리기
def boom(i, j, type):
    q = collections.deque()
    q.append((i, j))
    while q:
        ii, jj = q.popleft()
        for k in range(4):
            ni = ii + directions[k][0]
            nj = jj + directions[k][1]
            if 0 <= ni < 12 and 0 <= nj < 6 and arr[ni][nj] == type:
                q.append((ni, nj))
                # 터뜨리기(점으로 만들기)
                arr[ni][nj] = '.'


# 뿌요 아래로 이동시키기
def move():
    for j in range(6):
        blank = 11
        bbuyo = 11
        while blank >= 0  and bbuyo >= 0:
            if arr[blank][j] == '.':
                while bbuyo >= 0 and arr[bbuyo][j] == '.':
                    bbuyo -= 1
                if blank > bbuyo and bbuyo != -1:
                    arr[blank][j], arr[bbuyo][j] = arr[bbuyo][j], arr[blank][j]
                else:
                    bbuyo -= 1
            else:
                blank -= 1



directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
arr = list(list(input().strip()) for _ in range(12))
ans = 0

# 쭉 보면서 터질 그룹들이 있는지 판단하기
while True:
    flag = False
    for i in range(12):
        for j in range(6):
            if arr[i][j] != '.':
                cnt = bfs(i, j, arr[i][j])
                if cnt >= 4:  # 터뜨릴 수 있으면 터뜨리기
                    boom(i, j, arr[i][j])
                    flag = True


    move()
    if flag == False:
        break
    elif flag == True:
        ans += 1

print(ans)

boom()과 bfs()에 중복 코드가 많아서 없애고 싶었는데..
다른 분들 코드를 보면서 수정한 버전!! 중복도 없어지고 깔끔해졌다 😍😍

import collections
import sys

input = sys.stdin.readline


# 그 위치부터 봐서 같은 색 뿌요 개수 세기
def bfs(i, j, type):
    visited = [[False] * 6 for _ in range(12)]
    cnt = 1
    will_boom = []
    q = collections.deque()
    q.append((i, j))
    will_boom.append((i,j))
    visited[i][j] = True
    while q:
        ii, jj = q.popleft()
        for k in range(4):
            ni = ii + directions[k][0]
            nj = jj + directions[k][1]
            if 0 <= ni < 12 and 0 <= nj < 6 and visited[ni][nj] == False and arr[ni][nj] == type:
                cnt += 1
                will_boom.append((ni,nj))
                q.append((ni, nj))
                visited[ni][nj] = True
    return cnt, will_boom


# 터뜨리기
def boom(will_boom):
    for b in will_boom:
        i, j = b
        arr[i][j] = '.'


# 뿌요 아래로 이동시키기
def move():
    for j in range(6):
        blank = 11
        bbuyo = 11
        while blank >= 0  and bbuyo >= 0:
            if arr[blank][j] == '.':
                while bbuyo >= 0 and arr[bbuyo][j] == '.':
                    bbuyo -= 1
                if blank > bbuyo and bbuyo != -1:
                    arr[blank][j], arr[bbuyo][j] = arr[bbuyo][j], arr[blank][j]
                else:
                    bbuyo -= 1
            else:
                blank -= 1



directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
arr = list(list(input().strip()) for _ in range(12))
ans = 0

# 쭉 보면서 터질 그룹들이 있는지 판단하기
while True:
    flag = False
    for i in range(12):
        for j in range(6):
            if arr[i][j] != '.':
                cnt, will_boom = bfs(i, j, arr[i][j])
                if cnt >= 4:  # 터뜨릴 수 있으면 터뜨리기
                    boom(will_boom)
                    flag = True


    move()
    if flag == False:
        break
    elif flag == True:
        ans += 1

print(ans)