백준 알고리즘 11559번 Puyo Puyo(python)

구현 & DFS & BFS 문제이다. 기업 코딩 테스트에서 나올 것 같은 문제인데 참 재밌게 푼 것 같다.

1. 터트릴 뿌요가 있는지 확인하는 함수(같은 색깔의 뿌요가 4개 이상 뭉쳐 있는지 확인)

2. 뿌요를 터트려주는 함수('RGBPY' -> '0')

3. 상태를 업데이트해주는 함수(터진 뿌요가 있을 시 그 위치보다 위에 있는 뿌요들을 밑으로 내림)

위 3개의 함수를 구현해서 해결했다.

 

DFS 풀이

import sys
from copy import deepcopy
sys.setrecursionlimit(300000)

def dfs_check(y, x, color, cnt):
    b[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
            cnt = dfs_check(Y, X, color, cnt+1)
    return cnt


def dfs(y, x, color):
    a[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
            dfs(Y, X, color)
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if dfs_check(i, j, a[i][j], 1) >= 4:
                    dfs(i, j, a[i][j])
                    ok = 1
    update()
    if ok == 0:
        break
    combo += 1
print(combo)

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs_check(y, x, color):
    queue = deque()
    queue.append((y, x))
    b[y][x] = '0'
    cnt = 1
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
                b[Y][X] = '0'
                queue.append((Y, X))                
                cnt += 1
    return cnt

def bfs(y, x, color):
    queue = deque()
    queue.append((y, x))
    a[y][x] = '0'
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
                queue.append((Y, X))                
                a[Y][X] = '0'
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if bfs_check(i, j, a[i][j]) >= 4:
                    bfs(i, j, a[i][j])
                    ok = 1                
    update()
    if ok == 0:
        break
    combo += 1
print(combo)