[Python] G4 11559 Puyo Puyo

문제 풀이

dfs + 구현 문제이다.
1. 필드를 for문으로 탐색한다.
2. 필드 중 "."이 아닌 색깔의 뿌요일 경우 dfs 탐색을 한다.
3. 4개 이상 같은 색깔일 경우 터뜨려 "."으로 바꿔준다.
4. 필드 탐색을 끝냈을 때, 빈 공간을 채우며 색깔 뿌요들을 떨어뜨린다.
5. 이 과정을 더 이상 터뜨릴 뿌요가 없을 때까지 반복한다.

빈 공간을 채우며 색깔 뿌요들을 터뜨리는 부분이 좀 복잡했는데

def down():
    for i in range(6):
        for j in range(10, -1, -1):
            for k in range(11, j, -1):
                if graph[j][i] != "." and graph[k][i] == ".":
                    graph[k][i] = graph[j][i]
                    graph[j][i] = "."
                    break

i는 y 좌표이고, j랑 k가 x 좌표인데 j가 바닥부터 맨 위까지 이동하며 색깔 뿌요를 탐색하고, k는 그런 색깔 뿌요를 바닥까지 떨어뜨리기 위한 것이라고 보면 되는데

if graph[j][i] != "." and graph[k][i] == ".":

이 부분이 graph[j][i] 즉, j가 색깔 뿌요인지 확인하고, graph[k][i]는 바닥부터 j까지 이동하며 빈 공간을 확인해서 빈 공간으로 색깔 뿌요를 떨어뜨린다. 즉, 제일 밑에 있는 빈 공간으로 색깔 뿌요를 하나씩 떨어뜨린다는 것이다.

답

graph = []

movex = [0,1,0,-1]
movey = [1,0,-1,0]

for i in range(12):
    tmp = list(map(str,input()))
    graph.append(tmp)



def check_boom(i,j,color):
    global check_cnt,check_box
    for k in range(4):
        mx = i + movex[k]
        my = j + movey[k]
        if 0 <= mx < 12 and 0 <= my < 6 and check_box[mx][my] == 0 and graph[mx][my] == color:
            check_box[mx][my] = 1
            check_cnt += 1
            check_boom(mx,my,color)


def down():
    for i in range(6):
        for j in range(10, -1, -1):
            for k in range(11, j, -1):
                if graph[j][i] != "." and graph[k][i] == ".":
                    graph[k][i] = graph[j][i]
                    graph[j][i] = "."
                    break


global check_box,check_cnt
check_cnt = 0
cnt = 0
flag = 0
check_box = [[0] * 6 for _ in range(12)]
while True:
    for i in range(12):
        for j in range(6):
            if graph[i][j] != "." and check_box[i][j] == 0:
                check_box[i][j] = 1
                check_cnt = 1
                check_boom(i,j,graph[i][j])
                if check_cnt >= 4:
                    flag = 1
                    for w in range(12):
                        for e in range(6):
                            if check_box[w][e] == 1:
                                graph[w][e] = "."
                check_box = [[0] * 6 for _ in range(12)]
                check_cnt = 0
    if flag == 0:
        break
    cnt += 1
    flag = 0
    down()
print(cnt)