[BOJ] 11559. Puyo Puyo

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

11559번: Puyo Puyo

 

 

1. 해결방법

시뮬레이션 BFS 문제이다.
문제를 해결하는데 있어서 큰 어려움은 없었지만, 정답까지 오는데 많이 헤맸던 문제이다. 
3시간 정도 걸렸다.

쉽게 말해 애니팡과 같은 게임 종류의 문제이다. 알파벳을 터트리고 위에 있던 알파벳은 아래로 내려가는 로직으로 구성되어있다.

큐를 이용해서 2중 for문을 돌면서 알파벳이 있을 때, 큐에 담고 해당 알파벳과 일치하는 알파벳을 발견하면서 카운팅한다.
여기서 카운트가 4이상일 때, 해당 알파벳은 '.'으로 새로 갱신해주고 중력에 의해서 밑으로 이동해야한다.

그래비티 함수에서 2중 for문을 사용하였다. 중력때문에 밑에서부터 탐색을 해서 큐에 담고 큐를 차례대로 뽑아서 밑에서 부터 다시 채워넣는 로직이다.

주의해야될 점은 한번에 2번 알파벳이 펑 돼버리면 연쇄는 1로 적용된다는 것을 인지해야한다.
본인은 이 부분때문에 사용 시간의 절반을 쏟아부었다.

한번 탐색할 때, 여러 번 터지더라도 1 연쇄만 적용되므로 모든 탐색을 다 돌고 카운팅하도록 구현하였다.

 

 

2. 정답코드

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

# input
maps = [list(input().strip()) for _ in range(12)]


# bfs
def bfs(y, x):
    q.append((y, x))
    chk = [[False] * 6 for _ in range(12)]
    chk[y][x] = True
    alph = maps[y][x]
    count = 1
    alph_list = []
    x_list = []
    result = 0

    while q:
        ey, ex = q.popleft()
        alph_list.append((ey, ex))
        x_list.append(ex)
        for k in range(4):
            ny, nx = ey + dy[k], ex + dx[k]
            if 0 <= ny < 12 and 0 <= nx < 6:
                if chk[ny][nx] == False and maps[ny][nx] == alph:
                    chk[ny][nx] = True
                    q.append((ny, nx))
                    count += 1

    if count >= 4:
        result = 1
        for alph_y, alph_x in alph_list:
            maps[alph_y][alph_x] = '.'

    return result

# gravity
def gravity():
    gravity_q = deque()
    # 가로로 이동해서 탐색함
    for j in range(6):
        # 밑에서 부터 탐색해서 알파벳을 큐에 담음
        for i in range(11, -1, -1):
            if maps[i][j] == '.':
                continue
            else:
                gravity_q.append(maps[i][j])

        # 알파벳을 밑으로 이동(중력)
        for i in range(11, -1, -1):
            if gravity_q:
                maps[i][j] = gravity_q.popleft()
            else:
                maps[i][j] = '.'


# main
q = deque()
answer = 0
alpha = ['R', 'Y', 'G', 'P', 'B']
dy, dx = (0, 1, 0, -1), (1, 0, -1, 0)

while True:
    cnt = 0
    for i in range(12):
        for j in range(6):
            if maps[i][j] in alpha:
                cnt += bfs(i, j)

    if cnt == 0:
        print(answer)
        break
    else:
        answer += 1
        gravity()