[알고리즘] 백준 16768 Mooyo Mooyo / python, dfs, simulation

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

16768번: Mooyo Mooyo

 

✔ 문제 설명

N = 행의 수 (열은 10으로 고정)

K = 같은것이 K개일때 없앰

N=6, K=3일때를 예시로 들어보면, 같은 숫자가 3개이상일때 사라진다.

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

0000000000
0000000300
0054000300
1054500030
2200000000
0000000003

0000000000
0000000000
0000000000
0000000000
1054000300
2254500333

0000000000
0000000000
0000000000
0000000000
1054000000
2254500000

위의 과정을 거쳐 결과를 출력하면 된다.

✔ 풀이과정

dfs함수 : 값은 값이 K개 이상인 그룹이 있는지 확인하는 함수

dfs2함수 : 같은 값의 그룹을 삭제하는 함수

down함수 : 삭제한후에 값들을 밑으로 내리는 함수

N, K = map(int, input().split())
M = [list(input()) for _ in range(N)]
ck = [[False for i in range(10)] for _ in range(N)]
ck2 = [[False for i in range(10)] for _ in range(N)]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]

def dfs(x, y):
    ck[x][y] = True
    count = 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
        count += dfs(xx, yy)
    return count

def dfs2(x, y, m):
    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] != m:
            continue
        dfs2(xx, yy, m)

def down():
    for i in range(10):
        lst = []
        for j in range(N):
            if M[j][i] != '0':
                lst.append(M[j][i])
                M[j][i] = '0'
        for k in range(N-1, 0, -1):
            if lst:
                M[k][i] = lst.pop()

while True:
    exist = False
    ck = [[False for i in range(10)] for _ in range(N)]
    ck2 = [[False for i in range(10)] for _ in range(N)]
    for i in range(N):
        for j in range(10):
            if M[i][j] == '0' or ck[i][j]:
                continue
            count = dfs(i, j)
            if count >= K:
                dfs2(i, j, M[i][j])
                exist = True
    if not exist:
        break
    down()

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