[백준] 11559번 : Puyo Puyo

11559번: Puyo Puyo

해당 문제는 구현 문제로 상하좌우가 4개이상 연결되어 있는 판별과, 중력을 영향을 받아서 떨어지게되는 로직을 구현하면 된다.

1. 상하좌우가 4개이상 연결되어있는지 판별법
   1. 특정 모양에 대하여 기능을 나누었다.
   2. ㅗ,ㅜ,ㅏ,ㅓ 의 모양 : 특정 좌표에서 상하좌우로 탐색시 같은색상이 3 이상일때
   3. ㅁ 모양 : 특정 좌표에서 (1,0), (0,1), (1,1)이 같은 색상일때
   4. ㅡ,ㅣ 모양 : 특정 좌표에서 상하좌우로 탐색시 같은색상이 4 이상일때
2. 중력을 영향을 받아서 떨어지는 기능
   1. 각각의 열을 탐색한다.
   2. 각각의 열에대하여 아래서 부터 위까지 0이 아닌 색상을 큐에 추가한다.
   3. 각각의 열에대하여 큐에 추가된 블록을 아래서부터 채워나간뒤, 나머지 블록을 0으로 채운다.

from pprint import pprint
from collections import deque
N, M = 12, 6  # 높이가 12 가로가 6

shape = ((0, 1), (1, 0), (-1, 0), (0, -1))  # ㅗ, ㅜ, ㅏ, ㅓ
speicalshape = ((1, 0), (0, 1), (1, 1))  # 사각형 모양

graph = []

for _ in range(N):
    graph.append(list(map(str, input())))

def checkshpae2(i,j, color):
    queue = deque()
    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[i][j] = True
    queue.append((i, j, 1))
    while queue:
        y, x, cost = queue.popleft()
        if cost == 4: # ㅡ, ㅣ ... 모양
            return True

        for dy, dx in shape:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and M > nx >=0 and not visited[ny][nx]:
                visited[ny][nx] = True
                if graph[ny][nx] == color:
                    queue.append((ny, nx, cost + 1))

    return False

def checkshape(i, j, color):
    cnt = 0
    for dy, dx in shape:
        ny, nx = dy + i, dx + j
        if N > ny >= 0 and M > nx >= 0:
            if graph[ny][nx] == color:
                cnt += 1

    if cnt >= 3:
        return True
    else:
        return False

def checkspiecalshape(i,j, color):
    cnt = 0
    for dy, dx in speicalshape:
        ny, nx = dy +i, dx +j
        if N > ny >= 0 and M > nx >= 0:
            if graph[ny][nx] == color:
                cnt += 1

    if cnt == 3:
        return True
    else:
        return False

def puyopuyo(i, j, color):
    queue = deque()
    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[i][j] = True
    queue.append((i,j))
    while queue:
        y, x = queue.popleft()
        graph[y][x] = '.'
        for dy, dx in shape:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and M > nx >=0 and not visited[ny][nx]:
                visited[ny][nx] = True
                if graph[ny][nx] == color:
                    queue.append((ny, nx))

    return
def gravity():
    for i in range(M): # x좌표
        queue = deque()
        for j in range(N-1, -1, -1): # 아래서 부터 보면서 순차 큐에 넣는다.
            if graph[j][i] != '.':
                queue.append(graph[j][i])

        idx = N-1
        for t in queue: # Queue 에 있는값을 아래서부터 채운다.
            graph[idx][i] = t
            idx -= 1

        for t in range(idx, -1, -1): # 나머지부분은 빈칸으로 만들어준다.
            graph[t][i] = '.'

ans = 0
while True:
    cnt = 0
    for i in range(N):
        for j in range(M):
            #print(graph[i][j])
            if graph[i][j] != '.' and (checkshape(i,j, graph[i][j]) or checkspiecalshape(i,j, graph[i][j])or checkshpae2(i,j, graph[i][j])): # 모양의 조건이 맞다면
                puyopuyo(i,j, graph[i][j]) # 푸요푸요 한다.
                cnt += 1

    if cnt == 0: # 푸요푸요 할 것이 없다면 종료
        break

    gravity()
    #pprint(graph)
    ans += 1

print(ans)