[BOJ / 백준] 11559 Puyo Pyuo (G4 / 시뮬레이션, BFS) - Python

링크

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

 

 

 

 

문제 해석

입력
뿌요뿌요 판의 정보 (12 * 6)
  R G B P Y : 색상
  . : 빈 공간

 

출력
연쇄 수 / 없으면 0

 

 

초기 값에서는 아래 빈칸 없음

연쇄 == 턴
한 턴에 여러 색이 터지더라도 1연쇄

1. 뿌요가 존재하는 위치 찾기
2. bfs
3. 끌어내리기

 

 

풀이 & 코드 해석

BFS를 곁들인 시뮬레이션 문제입니다.

 

한 턴에 여러 개의 뿌요가 터지더라도 이는 1연쇄로 한다는 점을 잘 숙지하시면 크게 어려운 점이 없습니다.

 

 

 

 

코드

from collections import deque

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


def print_arr(arrs):
    for i in range(len(arrs)):
        for j in range(len(arrs[0])):
            print(arrs[i][j], end=" ")
        print()


def bfs(x, y):
    global is_puyo

    q = deque()
    q.append([x, y, arr[x][y]]) # 위치 및 색상 정보 저장

    puyo_data = [] # 연쇄가 일어날 위치 저장
    puyo_data.append([x, y])
    v = [[False] * 6 for _ in range(12)]
    v[x][y] = True

    while(len(q) != 0):
        px, py, pc = q.popleft()

        for d in range(4):
            nx = dx[d] + px
            ny = dy[d] + py

            if nx < 0 or nx >= 12 or ny < 0 or ny >= 6 or v[nx][ny] == True:
                continue

            if arr[nx][ny] == pc:
                q.append([nx, ny, pc])
                puyo_data.append([nx, ny])
                v[nx][ny] = True

    # 4개 이상이면 터뜨리기
    if len(puyo_data) >= 4:
        is_puyo = True
        for nx, ny in puyo_data:
            arr[nx][ny] = '.'


def drop():
    for j in range(6):
        for i in range(11, 0, -1):
            if arr[i][j] == '.':
                for ii in range(i - 1, -1, -1):
                    if arr[ii][j] != '.':
                        arr[i][j] = arr[ii][j]
                        arr[ii][j] = '.'
                        break


arr = []

for i in range(12):
    arr.append(list(map(str, input().strip())))

ans = 0

while True:
    # print_arr(arr)
    # print()
    is_puyo = False
    # 뿌요 존재하는 위치 찾기
    for i in range(12):
        for j in range(6):
            if arr[i][j] != '.':
                # bfs
                bfs(i, j)

    # 끌어내리기
    drop()

    # 연쇄가 없으면 끝내기
    if is_puyo == False:
        break
    else:
        ans += 1

# 빠요엔!
print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java