백준 11559번 Puyo Puyo

문제 설명

 

dx, dy는 상하좌우에 같은 색깔의 뿌요가 있는지 확인할 때 사용한다. refresh 함수는 뿌요가 터지고 뿌요들을 다시 아래로 떨어지게 하는 함수다. color 배열에 해당 열에 있는 모든 색들을 넣고 가장 아래서부터 차례대로 채워넣는다.

 

 

 

 

boom_count는 연쇄가 일어나는지 판별하기 위한 변수다. cur_color는 해당 위치의 뿌요의 색깔을 의미하고 color_count는 해당 뿌요와 같은 색깔의 뿌요의 갯수를 뜻한다. dfs를 사용하여 queue에 뿌요를 넣고 인접하는 같은 색깔의 뿌요를 same_color에 넣는다.

 

 

만약 인접한 같은 색깔의 뿌요가 3개 이상일 경우 boom_count를 1 더해주고 뿌요들을 . 으로 바꾼후 refresh 함수를 호출한다. 이중 for문을 돌린 후에도 boom_count가 0이면 연쇄할 뿌요가 없다는 뜻이므로 함수를 종료한다. 

 

 

전체 코드

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


def refresh():
    global board
    for j in range(6):
        colors = []
        for i in reversed(range(12)):
            if board[i][j] != '.':
                colors.append(board[i][j])
        i = 11
        for color in colors:
            board[i][j] = color
            i -= 1
        while i >= 0:
            board[i][j] = '.'
            i -= 1


def func(arr):
    global board
    global answer
    while True:
        boom_count = 0
        for i in range(12):
            for j in range(6):
                if arr[i][j] == '.':
                    continue
                cur_color = arr[i][j]
                color_count = 0
                queue = []
                same_color = []
                queue.append([i, j])
                same_color.append([i, j])
                while queue:
                    cur = queue.pop(0)
                    for k in range(4):
                        cur_x = cur[0] + dx[k]
                        cur_y = cur[1] + dy[k]
                        if cur_x < 0 or cur_x > 11 or cur_y < 0 or cur_y > 5:
                            continue
                        if arr[cur_x][cur_y] == '.':
                            continue
                        if [cur_x, cur_y] in same_color:
                            continue
                        if arr[cur_x][cur_y] == cur_color:
                            color_count += 1
                            queue.append([cur_x, cur_y])
                            same_color.append([cur_x, cur_y])
                if color_count >= 3:
                    boom_count += 1
                    for index in same_color:
                        arr[index[0]][index[1]] = '.'

        if boom_count == 0:
            break
        answer += 1
        refresh()
    return


def main():
    global board
    global answer
    for i in range(12):
        board.append(list(map(str,input())))
    func(board)
    print(answer)
    return

if __name__ == "__main__":
    main()