[백준] 11559 PuyoPuyo

백준 11559번 Puyo Puyo

구현 / 그래프 / 너비우선탐색 / 시뮬레이션

 

 

[문제]

 

2시간 반이 걸린 문제^^

시뮬레이션 문제가 어렵다는걸 느꼇다.

 

상하좌우연결을 보고 탐색이 필요할 것 같고 아래로 내려오는 별도의 함수도 구현해야 하겠다는 생각을 할 수 있었다.

 

 

 

[과정]

 

기본적인 로직 : 모든 배열의 자리에서 상하좌우를 비교하고 하나가 터지면 자리를 내리고 계속 비교하는 것

 

※ 핵심이 되는 부분

• 모든 자리에서 bfs를 돌릴 때 4개 이상의 같은 좌표가 있어서 사라지게 되면 바로 내려오는 것이 아니고, 모든 좌표에서 같은 arr배열을 사용해서 bfs를 돌리고 내려오지 않은 상태로 마지막까지 반복하는 것
• 사라진 좌표는 별도의 배열에 저장하고 arr배열의 해당 좌표값을 . 으로 바꾼 후 좌표가 터진 횟수(cnt)를 저장함
• cnt를 bfs돌릴 때 마다 갱신하기 위해서 매개변수로 넣어줌

모든 좌표에서 bfs가 끝났다면 arr배열의 상태는 터진 부분이 있다면 군데 군데가 . 으로 바뀐 상태일 것

• cnt(터진 횟수)를 비교해서 cnt가 0이라면 ans를 출력하고 무한루프를 끝냄
• cnt가 1이상이라면 터진곳의 위의 값들을 아래로 내려주는 작업(check_fall)이 필요하므로 전체 반복 횟수(ans)를 1 증가시켜주고 좌표를 위에서 아래로 내려줌(check_fall())

위의 로직을 무한루프 실행

 

 

※ 크게 본 로직

• 모든 자리에서 해당 좌표가 . 이 아닌 경우에 bfs 실행
• bfs()
  • 이어진 좌표가 4개 이상일 경우 cnt를 1 증가 시켜준 후 찾은 좌표들의 값을 모두 . 으로 바꿔준 후 cnt 반환
• check_fall() 
  • 마지막행-1(10)의 인덱스 위치에서 부터 위로 반복문 실행
  • 현재 값과 아래의 값을 비교하여 아래의 값이 비어있고 현재 값이 비어있지 않으면 해당 인덱스까지 위에서 부터 한칸씩 내려주기
  • 마지막 좌표는 . 으로 변환

 

 

[소스코드]

# 11559 Puyo Puyo

from collections import deque
import sys
input = sys.stdin.readline

arr = [list(input()) for _ in range(12)]
dx,dy = [-1,1,0,0], [0,0,-1,1]

def bfs(x_,y_,visited, cnt):
    q = deque()
    q.append((x_,y_))
    result = []
    visited[x_][y_] = True

    while q:
        x,y = q.popleft()
        result.append([x,y])

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < 12 and ny >= 0 and ny < 6:
                if visited[nx][ny]:
                    continue
                if arr[nx][ny] == arr[x][y]:
                    visited[nx][ny] = True
                    q.append((nx,ny))
    if len(result) >= 4:
        cnt += 1
        for re in result:
            arr[re[0]][re[1]] = '.'
    return cnt

def check_fall():
    for i in range(10, -1, -1):
        for j in range(6):
            if arr[i][j] != '.' and arr[i+1][j] == '.':
                for k in range(i+1, 12):
                    if k == 11 and arr[k][j] == '.':
                        arr[k][j] = arr[i][j]
                    elif arr[k][j] != '.':
                        arr[k-1][j] = arr[i][j]
                        break
                arr[i][j] = '.'

ans = 0
while True:
    # 모든 data의 자리에서 상하좌우 비교
    # 하나가 터지면 자리를 내리고 계속 비교
    cnt = 0
    for i in range(12):
        for j in range(6):
            visited = [[False] * 6 for _ in range(12)]
            if arr[i][j] != '.':
                cnt = bfs(i,j,visited, cnt)
    if cnt == 0:
        print(ans)
        break
    else:
        ans += 1
    check_fall()

 

---

 

[통과]