[백준 2024/02/20] 11559번 Puyo Puyo

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

11559번: Puyo Puyo

 

1. 접근 방법

뿌요 뿌요라는 게임을 알고 있었기 때문에 코딩을 짜면서 재밌었다. ㅎㅎㅎ

 

이번 문제는 같은 색에 대해서 상하좌우로 연결이 되어 있는 것이 4개 이상이라면, pop을 해주는 것이다. 

https://potatoscatteringsmile.tistory.com/118

[백준 2024/02/15] 2667번 단지번호붙이기

이 문제와 아주 유사하다고 생각이 들었다. 이 문제도 상하좌우로 얼마나 많은 집들이 연결되어 있느냐를 구하는 문제였기 때문이다.

 

def chain(x, y, color):
    if (0 <= x < 12) and (0 <= y < 6) and grid[x][y] == color:
        grid[x][y] = '.'
        save.append([x, y, color])
        return 1 + chain(x-1, y, color) + chain(x+1, y, color) + chain(x, y-1, color) + chain(x, y+1, color)
    return 0

따라서 chain이라는 함수로 연결되어 있는 뿌요들을 pop 해주었다. 

하지만, 이 함수는 몇개가 연결되어 있는지 구하면서 grid[x][y] = '.'을 해주기 때문에 4개 이상이 붙어 있지 않을 경우, 원래의 값을 복원해 주어야 한다.

 

따라서 save.append([x, y, color]) 를 통해 지우는 값들을 계속 저장해두었다. 

 

return 값이 4 이하일 경우 (붙어 있는 뿌요들이 4 이하일 경우) restore() 함수를 호출해 주었다.

restore 함수에서 save에 저장되어 있는 값들을 하나씩 불러와서 new_grid라는 곳에 저장해 두었다. 

def restore():
    for x, y, color in save:
        new_grid[x][y] = color

 

이후 grid에 new_grid의 값을 넣어주고, new_grid는 다시 restore()함수에서 이용하기 위해 '.'을 다 저장해 주었다.

new_grid = [['.' for _ in range(6)] for _ in range(12)]

 

이후 grid에 저장되어 있는 값들을 중력에 따라 밑으로 내려줘야 한다.

2중 for 문에서, 자기 자신이 grid[x][y] 가 '.'이 아니고, grid[x+1][y] 가 '.' 일 때, 밑으로 값을 내려준다.

이때 y 밑에 index 부터 0번 index까지 올라가야 한다. 그래야지, 밑에서 부터 차근차근 땅으로 내려준다.

 

2. 코드

def chain(x, y, color):
    if (0 <= x < 12) and (0 <= y < 6) and grid[x][y] == color:
        grid[x][y] = '.'
        save.append([x, y, color])
        return 1 + chain(x-1, y, color) + chain(x+1, y, color) + chain(x, y-1, color) + chain(x, y+1, color)
    return 0

def restore():
    for x, y, color in save:
        new_grid[x][y] = color

def gravity(x, y):
    if (0<= x+1 < 12) and grid[x][y] != '.' and grid[x+1][y] == '.':
        grid[x+1][y] = grid[x][y]
        grid[x][y] = '.'
        return gravity(x+1, y)
    return


if __name__ == '__main__':
    rows = 12
    grid = []
    save = []
    popped = True
    popped_time = -1

    for _ in range(rows):
        line = input()
        grid.append(list(line))

    while popped == True:
        popped = False
        popped_time += 1
        new_grid = [['.' for _ in range(6)] for _ in range(12)]
        for j in range(0, 12, 1):
            for i in range(0, 6, 1):
                if grid[j][i] != '.':
                    if chain(j, i, grid[j][i]) < 4:
                        restore()
                    else:
                        popped = True
                    save = []
                    
        grid = [row[:] for row in new_grid]
        for y in range(0, 6, 1):
            for x in range(11, -1, -1):
                gravity(x, y)

    print(popped_time)