BOJ - 16768 - Mooyo Mooyo

Updated:

import sys
from collections import deque

def BFS(Field, i, j, mooyo, check, N, K):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    dq = deque()
    block = [[i, j]]
    dq.append((i, j))
    check[i][j] = True

    while dq:
        x, y = dq.popleft()
        for step in range(4):
            nx, ny = x + dx[step], y + dy[step]
            if 0 <= nx < N and 0 <= ny < 10:
                if not check[nx][ny] and Field[nx][ny] == mooyo:
                    check[nx][ny] = True
                    block.append([nx, ny])
                    dq.append((nx, ny))

    if len(block) >= K:
        for x, y in block:
            Field[x][y] = '0'
        return True

    else:
        return False

def MooyoFall(Field, N):
    for i in range(10):
        for j in range(N-1, -1, -1):
            if Field[j][i] == '0':
                continue
            for k in range(N-1, j-1, -1):
                if Field[k][i] == '0':
                    Field[k][i] = Field[j][i]
                    Field[j][i] = '0'


def MooyoCrash(Field, N, K):
    isCrash = False

    check = [[False for _ in range(10)] for _ in range(N)]
    for i in range(N-1, -1, -1):
        for j in range(10):
            if Field[i][j] != '0':
                if not check[i][j]:
                    if BFS(Field, i, j, Field[i][j], check, N, K):
                        isCrash = True

    return isCrash

def solution():
    N, K = map(int, sys.stdin.readline().split())
    Field =[]
    for _ in range(N):
        Field.append(list(map(str, sys.stdin.readline().strip())))

    while MooyoCrash(Field, N, K):
        MooyoFall(Field, N)

    for i in range(N):
        for j in range(10):
            print(Field[i][j], end='')
        print()

solution()

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

Categories:

Updated:

Leave a comment