[Baekjoon] 16768. Mooyo Mooyo

# Problem

With plenty of free time on their hands (or rather, hooves), the cows on Farmer John's farm often pass the time by playing video games. One of their favorites is based on a popular human video game called Puyo Puyo; the cow version is of course called Mooyo Mooyo. The game of Mooyo Mooyo is played on a tall narrow grid N cells tall (1≤N≤100) and 10 cells wide. Here is an example with N=6: Each cell is either empty (indicated by a 0), or a haybale in one of nine different colors (indicated by characters 1..9). Gravity causes haybales to fall downward, so there is never a 0 cell below a haybale.   Two cells belong to the same connected region if they are directly adjacent either horizontally or vertically, and they have the same nonzero color. Any time a connected region exists with at least K cells, its haybales all disappear, turning into zeros. If multiple such connected regions exist at the same time, they all disappear simultaneously. Afterwards, gravity might cause haybales to fall downward to fill some of the resulting cells that became zeros. In the resulting configuration, there may again be connected regions of size at least K cells. If so, they also disappear (simultaneously, if there are multiple such regions), then gravity pulls the remaining cells downward, and the process repeats until no connected regions of size at least K exist. Given the state of a Mooyo Mooyo board, please output a final picture of the board after these operations have occurred. 입력 The first line of input contains N and K (1≤K≤10N). The remaining N lines specify the initial state of the board. 출력 Please output N lines, describing a picture of the final board state.

 

# My Answer

n,k = map(int,input().split())
board=list()

for _ in range(n):
    board.append(list(map(int,list(input()))))

dx,dy = [-1,1,0,0],[0,0,1,-1]
pos=list()

def dfs(b,x,y):
    global pos,visited,board
    if board[x][y]==b:
        pos[-1].append((x,y))
        visited[x][y]=True
        for q in range(4):
            xx,yy = x+dx[q],y+dy[q]
            if xx<0 or xx>=n or yy<0 or yy>=10:
                continue
            if not visited[xx][yy]:
                dfs(b,xx,yy)
    else:
        return
def process():
    global pos,visited,board
    pos=[]
    visited=[[False]*10 for _ in range(n)]
    for i in range(n):
        for j in range(10):
            if board[i][j]!=0 and not visited[i][j]:
                visited[i][j]=True
                pos.append([])
                pos[-1].append((i,j))
                for d in range(4):
                    ii,jj = i+dx[d],j+dy[d]
                    if ii<0 or ii>=n or jj<0 or jj>=10:
                        continue
                    if not visited[ii][jj]:
                        dfs(board[i][j],i+dx[d],j+dy[d])

    max_len=0
    for p in pos:
        max_len = max(max_len,len(p))
    if max_len <k:
        for b in board:
            for h in b:
                print(h,end='')
            print()
        exit(0)
    for p in pos:
        if len(p)>=k:
            for a,b in p:
                board[a][b]=0

    for _ in range(n):
        for l in range(n-2,-1,-1):
            for m in range(10):
                if board[l][m]!=0 and board[l+1][m]==0:
                    board[l][m],board[l+1][m] = board[l+1][m],board[l][m]
        
while True:
    process()

상하좌우 k개 연결되어 있으면 동시 삭제 - 0으로 바꿈 ( 위부터 )
0 위에 숫자 있을 수 없음 - 0위의 숫자들은 아래로 내리기 ( 아래부터 탐색 )
k개 연결된 그룹 없을 때까지 반복

 

# Solution

def new_array(N):
    return [[False for i in range(10)] for _ in range(N)]

N, K= map(int,input().split())
M = [list(input()) for _ in range(N)]
ck = new_array(N)
ck2 = new_array(N)

dx,dy = [-1,1,0,0],[0,0,1,-1]
def dfs(x,y):
    ck[x][y] = True
    ret=1
    for i in range(4):
        xx,yy = x+dx[i],y+dy[i]
        if xx<0 or xx>=N or yy<0 or yy>=10:
            continue
        if ck[xx][yy] or M[x][y] != M[xx][yy]:
            continue
        ret += dfs(xx,yy)
    return ret
        
def dfs2(x,y,val):
    ck2[x][y] = True
    M[x][y]='0'
    for i in range(4):
        xx,yy = x+dx[i],y+dy[i]
        if xx<0 or xx>=N or yy<0 or yy>=10:
            continue
        if ck2[xx][yy] or M[xx][yy] != val:
            continue
        dfs2(xx,yy,val)
        
def down():
    for i in range(10):
        tmp = []
        for j in range(N):
            if M[j][i]!='0':
                tmp.append(M[j][i])
        for j in range(N-len(tmp)):
            M[j][i]='0'
        for j in range(N-len(tmp),N):
            M[j][i]= tmp[j-(N-len(tmp))]
while True:
    exist = False
    ck = new_array(N)
    ck2 = new_array(N)
    for i in range(N):
        for j in range(10):
            if M[i][j] == '0' or ck[i][j]:
                continue
            res = dfs(i,j)
            if res >=K:
                dfs2(i,j,M[i][j])
                exist=True
    
    if not exist:
        break
    down()

for i in M:
    print(''.join(i))

dfs - k개 연결된 그룹 찾기

dfs2 - k개 연결된 그룹 지우기

down - 지운 부분 0보다 위에 있는 숫자 내리기 ( 세로로 )

             0 인 것과 아닌 것 나눠서 저장하고 0인 것부터 위에서 부터 채운 후 남은 자리에 숫자 저장 순서대로 채운다