[백준] Puyo Puyo - 11559번

문제

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

11559번: Puyo Puyo

 

해석 및 풀이

 

 뭔가 내가 요즘 많이 보고 잘 풀고 싶은 유형이다. '시뮬레이션 + 연쇄 반응'  그런데 이 문제는 그런 유형 중에서도 살짝 쉬운 버전인 것 같다.

 쉽다고 생각한 이유는 처음 생각대로 문제를 풀면 풀리는 것 같아서다ㅎ...

 

1. bfs를 이용한 터질 뿌요 찾기

2. 터진 뿌요를 제외한 놈들을 중력을 이용해 내려주기

 

뿌요의 공간이 12 * 6 이여서 어떻게 풀더라도 시간초과가 날 것 같지는 않다.

 

1 의 경우에는 말 그대로 12 * 6 의 공간을 bfs를 이용해 훑으며 직접 확인했고, 동일한 뿌요가 상하좌우에 4개 이상이라면 해당 자리를 비워주는 형식으로 구현했다.

2는 6개의 col을 row의 아래에서 부터 올라가며 빈공간을 제외한 뿌요만 stack에 담아 다시 row의 아래에서부터 쌓아줬다.

 

여담으로 함수의 분리가 확실히 구현할때 편리한 것 같다

구현

 

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

for i in range(12):
    world.append(list(input()))
answer = 0

# bfs로 체크하고, 내려버리기 시전
isVisited = [[0 for _ in range(6)] for _ in range(12)]

def clearVisited():
    global isVisited
    isVisited = [[0 for _ in range(6)] for _ in range(12)]

puyo = []
def bfsChecker(x, y):
    global answer
    global puyo
    q = deque()
    q.append([x, y, world[x][y]])
    isVisited[x][y] = 1
    temppuyo = []
    while q:
        curx, cury, target = q.popleft()
        temppuyo.append([curx, cury])
        for i in range(4):
            nx = curx + dx[i]
            ny = cury + dy[i]
            if 0 <= nx < 12 and 0 <= ny < 6 and world[nx][ny] == target and isVisited[nx][ny] == 0:
                q.append([nx, ny, target])
                isVisited[nx][ny] = 1

    # 같은 뿌요가 4개 이상일때만 유효함
    if len(temppuyo) >= 4:
        puyo += temppuyo


def gravity():
    global world
    for i in range(6):
        stack = []
        for j in range(12):
            if world[11 - j][i] != '.':
                stack.append(world[11-j][i])
                world[11 - j][i] = '.'
        for idx, value in enumerate(stack):
            world[11-idx][i] = value


while True:
    for i in range(12):
        for j in range(6):
            if world[i][j] != '.' and isVisited[i][j] == 0:
                bfsChecker(i, j)

    if len(puyo) >= 4:
        for x, y in puyo:
            world[x][y] = '.'
        clearVisited()
        gravity()
        answer += 1
        puyo = []
    else:
        break


print(answer)

 

 

 

비슷한 중력 문제 유형으로 

https://driveitlikeyoustoleitt.tistory.com/entry/백준-falling-apples-13732번

[백준] falling apples - 13732번

요것 추천합니다!!

 

끘~~