[Python] 백준 16768번 Mooyo Mooyo

| 문제 내용

뿌요뿌요 게임과 유사하게, K개 이상의 같은 숫자가 연속해서 나타나면 해당 그룹이 동시에 터지며, 그 위의 숫자들이 아래로 내려오게 된다. 더 이상 터질 그룹이 없을 때의 숫자 배열을 출력하는 문제

 

| 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

# 체크 배열 생성용
def new_arr(N):
    return [[0 for _ in range(10)] for _ in range(N)]

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

dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]

# 같은 숫자 그룹내 숫자 개수 세기
def dfs(x, y):
    ck[x][y] = True
    ret = 1 # 그룹 내 숫자 수

    # x,y 좌표 기준으로 깊이 우선으로 사방 체크
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= N or ny < 0 or ny >= 10:
            continue
        if ck[nx][ny] or M[x][y] != M[nx][ny]:
            continue
        ret += dfs(nx, ny)
    return ret

# 그룹 내 숫자 모두 제거(0으로)
def dfs2(x, y, val):
    # dfs와 같음.
    ck2[x][y] = True # 삭제할 때 확일할 체크 배열. 숫자세는 것과 별개로 삭제했는지 여부는 따로 체크
    M[x][y] = 0 # 삭제 처리

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if nx < 0 or nx >= N or ny < 0 or ny >= 10:
            continue
        if ck2[nx][ny] or M[nx][ny] != val:
            continue
        dfs2(nx, ny, val)

# Map내에서 0이 아닌 숫자 그룹 아래로 내리기
def down():
    # 열을 기준으로 0이 아닌 숫자 확인
    for i in range(10):
        tmp = []
        for j in range(N):
            if M[j][i] != 0:
                tmp.append(M[j][i])
        # 숫자 위쪽은 0으로 채우기
        for j in range(N - len(tmp)):
            M[j][i] = 0
        # tmp에 저장된 valid 숫자로 채우기
        for j in range(N - len(tmp), N):
            M[j][i] = tmp[j - (N - len(tmp))]

# 맵에 대해 더이상 변경사항이 없을 때까지 반복문 실행
while True:
    exist = False
    # 반복문 새로 돌때마다 갱신
    ck = new_arr(N)
    ck2 = new_arr(N)

    for i in range(N):
        for j in range(10):
            if ck[i][j] or M[i][j] == 0:
                continue
            res = dfs(i, j) # 그룹 내 숫자 세기
            if res >= K:
                dfs2(i, j, M[i][j]) # 현재 위치부터 해당 숫자그룹 모두 제거
                exist = True
    # Map 한 바꾸 돌았을 때 더이상 변경사항이 없으면 반복문 종료
    if not exist:
        break
    # 숫자칸 내리기
    down()

for i in M:
    print(''.join(map(str, i)))

 

| 느낀점

문제를 어떻게 풀어야하는 지는 감이 오는데 아직도 구현 자체가 어렵고 시간이 오래걸린다. 비슷한 문제를 여러개 풀어봐야겠다.