[백준] 11559 puyopuyo (파이썬 python)

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

11559번: Puyo Puyo

---

bfs를 잘 사용하면 되는 문제.

---

아이디어

---

전체 코드

from collections import deque
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
field_info = []

for _ in range(12):
    field_info.append(list(input()))

def bfs(a, b, c):
    global boom_flag
    boom_list = []
    deq = deque()

    deq.append([a,b])
    boom_list.append([a,b])

    field_check[a][b] = True

    n = 1

    while deq:
        x, y = deq.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 12 and 0 <= ny < 6:
                if field_info[nx][ny] == c and not field_check[nx][ny]:
                    field_check[nx][ny] = True
                    deq.append([nx,ny])
                    boom_list.append([nx,ny])
                    n += 1

    if n >= 4:
        for b in boom_list:
            field_info[b[0]][b[1]] = '.'

        boom_flag = True

boom_count = 0

while True:
    boom_flag = False

    field_check = [[False] * 6 for _ in range(12)]

    for i in range(12):
        for j in range(6):
            if field_info[i][j] != '.':
                bfs(i,j,field_info[i][j])


    for i in range(6):
        rotate_queue = deque()

        for j in range(11,-1,-1):
            if field_info[j][i] != '.':
                rotate_queue.append(field_info[j][i])

        for j in range(11,-1,-1):
            if rotate_queue:
                field_info[j][i] = rotate_queue.popleft()
            else:
                field_info[j][i] = '.'

    if not boom_flag:
        break
    else:
        boom_count += 1

print(boom_count)

---

코드 설명

1. bfs

for i in range(12):
    for j in range(6):
        if field_info[i][j] != '.':
            bfs(i,j,field_info[i][j])

필드에 있는 모든 칸에 대해 빈칸('.')인지 아닌지 확인하고 빈칸이 아니면 bfs를 실행한다.

bfs 함수는 아래와 같다.

 

def bfs(a, b, c):
    global boom_flag
    boom_list = [] # 터트릴 위치를 저장
    deq = deque() # bfs를 위한 큐

    deq.append([a,b]) 
    boom_list.append([a,b])

    field_check[a][b] = True

    n = 1 #뿌요 개수

    while deq:
        x, y = deq.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 12 and 0 <= ny < 6:
                if field_info[nx][ny] == c and not field_check[nx][ny]:
                    field_check[nx][ny] = True
                    deq.append([nx,ny])
                    boom_list.append([nx,ny])
                    n += 1 #블럭 개수 +1 

    if n >= 4:
        for b in boom_list:
            field_info[b[0]][b[1]] = '.' #터진곳은 빈칸으로 변경

        boom_flag = True #터짐

bfs 하면서 입력받았던 블록의 색깔 c와 같고 아직 방문하지 않은 칸이면 큐에 추가해 준다.

연결된 뿌요 개수가 4개 이상이라면 빈칸으로 변경해 주고, flag를 true로 바꿔준다.

 

2. 뿌요 내리기

for i in range(6):
    rotate_queue = deque()

    for j in range(11,-1,-1):
        if field_info[j][i] != '.':
            rotate_queue.append(field_info[j][i])

    for j in range(11,-1,-1):
        if rotate_queue:
            field_info[j][i] = rotate_queue.popleft()
        else:
            field_info[j][i] = '.'

빈칸을 채워주는 코드다. 각 열마다, 밑에서부터 스캔하며 뿌요를 rotate_queue에 넣어주고, 

다시 밑에서부터 차례대로 뿌요를 쌓아준다. 전부 다 쌓고 난 뒤 빈칸으로 채워준다.