(Python) 백준 11559번: Puyo Puyo

 

출처 : https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

---

 

---

 

(Python) 백준 11559번: Puyo Puyo¶

출처 : https://www.acmicpc.net/problem/11559

• 알고리즘 분류
  • BFS
  • DFS
  • 시뮬레이션

---

In [1]:

from collections import deque

In [2]:

def bfs(x, y, color):
    same_color = set()
    queue = deque()
    queue.append((x,y))
    
    while queue:
        node = queue.popleft()
        if node in same_color: continue
        same_color.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
            if board[nx][ny] == color:
                queue.append((nx, ny))
    return same_color

In [3]:

def fall():
    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] = '.'

In [4]:

if __name__ == '__main__':
    anv = 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):
        check = 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 check == 0: check = 1
                    for x, y in array:
                        board[x][y] = '.'
        fall()
        if check == 1: anv = anv + 1
        elif check == 0: break
    print(anv)

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.
3