[백준] 11559번 : Puyo Puyo - Python(파이썬)

문제

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

풀이

• DFS : 같은 색 & 이어진 뿌요 탐색
• que : 현재 위치 중심으로 사라질 뿌요 탐색
• set : 색깔 상관없이 사라질 모든 뿌요 집합 (=DFS에서 조건 만족한 모든 뿌요)
• 뿌요 내리기 : 밑에서부터 시작 / 위에 뿌요 있으면 . 과 바꿔주기
• While : flag 켜져 있으면 연쇄 횟수 증가, flag 꺼지면 반복문 탈출

 

 

 

코드

#문제 https://www.acmicpc.net/problem/11559


from collections import deque



def BFS(x, y,color): #터질 뿌요 탐색
    colors=set()
    que=deque()
    que.append((x,y))

    while que:
        node = que.popleft()
        if node in colors: continue
        colors.add(node)
        for i in range(4): #범위내 같은 색깔 탐색
            nx, ny = node[0]+dx[i], node[1]+dy[i]
            if not(0<=nx<n and 0<=ny<m): continue #game 보드 내 범위 아님
            if board[nx][ny] == color: #같은 색
                que.append((nx, ny)) #큐에 추가 -> while 돌며 추가된 위치 중심으로 다시 탐색
    return colors


def down():
    for y in range(m):
        for x in range(n-1, -1, -1):
            if board[x][y] == '.': continue
            for k in range(n-1, x, -1):
                if board[k][y] == '.':
                    board[k][y] = board[x][y]
                    board[x][y] = '.'



cnt = 0
n, m = 12, 6
board = [list(input().strip()) for _ in range(n)]

dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)

while(1):
    flag = 0
    for i in range(n-1, -1, -1):
        for j in range(m):
            if board[i][j] == '.': continue
            array = BFS(i, j, board[i][j])
            if len(array) >= 4:
                if flag == 0: flag = 1 #연쇄 Flag
                for x, y in array:
                    board[x][y] = '.'
    down()
    if flag == 1: cnt = cnt + 1 #연쇄 횟수 추가
    elif flag == 0: break
print(cnt)