[python] 11559 - Puyo Puyo

11559번: Puyo Puyo (acmicpc.net)

11559번: Puyo Puyo

 

보자마자 지난번에 풀었던 카카오 프렌즈 블록 문제랑 비슷하다고 생각했다.

그래서 일부 필요한 부분의 로직을 적용하였다.

 

우선 접근 단계는 다음과 같다.

 

1. 같은 색의 뿌요들이 4개 이상 모일 경우 터뜨린다.

2. 뿌요들이 터지면 아래가 비지 않게 하기 위하여 아래로 떨어트린다.

3. * 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 연쇄는 한 번이다.

 

3번 조건을 제대로 안읽고 풀어서 테스트케이스는 통과했지만

답은 계속 틀렸다.

문제를 꼼꼼히 읽자..! 

 

우선, 같은 색의 뿌요들을 탐색하기 위해 bfs를 이용하였다.

bfs에서 탐색하며 같은 색의 뿌요 개수를 세어주는 체크 리스트를 생성하여

4개 이상하면 리턴값을 반환하고

그렇지 않을 경우 0을 반환하였다.

 

이 부분이 중요한데,

3번 조건을 만족 시키기 위해서 리턴값을 반환해 주었다.

 

그리고 drop 함수를 만들어

뿌요 리스트를 끝에서부터 탐색하며

비어있는 부분을 위에있는 문자로 채워지게끔 하였다.

전에 카카오 문제 풀 때를 기억하며 해결하여서 크게 어려운 점은 없었다.

 

마지막으로 while문으로 뿌요 리스트를 탐색한다.

 

이중 for문을 돌며 bfs로 탐색한 값이 0이 아닐 경우,

즉 한 번이라도 터진 경우 !

계속 while문을 진행하며, 

for문이 끝나면 연쇄를 1 증가 시키고 drop 함수를 실행하여

빈자리를 채워준다.

 

탐색 값이 0인 경우 터진 뿌요가 없다는 말이므로 

while문을 종료한다.

 

3번 조건때문에 시간은 좀 걸렸지만 반복해서 꼼꼼하게 코드를 확인해 볼 수 있어서

도움이 많이 되었던 것 같다.

 

#11559 뿌요뿌요

import sys
from collections import deque

input = sys.stdin.readline

lst = [list(str(input().strip())) for _ in range(12)]

# test
# lst=[['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.'], ['.', 'Y', '.', '.', '.', '.'], ['.', 'Y', 'G', '.', '.', '.'], ['R', 'R', 'Y', 'G', '.', '.'], ['R', 'R', 'Y', 'G', 'G', '.']]


#같은 것 탐색
dxL=[0,0,-1,1]
dyL=[1,-1,0,0]    

def bfs(i,j,k):
    q = deque()
    q.append((i,j,k))
    lst[i][j] = '.'
    chk=[]
    while q:
        i,j,k = q.popleft()
        chk.append((i,j,k))
        
        for a in range(4):
            dx = i+dxL[a]
            dy = j+dyL[a]
           
            if dx < 0 or dx > 11 or dy <0 or dy > 5:
                continue
           
            if lst[dx][dy] == k and lst[dx][dy] != '.' and (dx,dy,k) not in chk:
                lst[dx][dy] = '.'
                q.append((dx,dy,k))
    #개수 체크
    if len(chk)>=4:
        return len(chk)
    else:
        for x,y,k in chk:
            lst[x][y] = k
        return 0
        
    
#떨어트리기                
def drop():
    for i in range(11, -1, -1):
        for j in range(5, -1, -1):
            if lst[i][j] == '.':
                x = i-1
                while x>=0 and lst[x][j] == '.':
                    x -=1
                if x<0:
                    lst[i][j] = '.'
                else:
                    lst[i][j] = lst[x][j]
                    lst[x][j] = '.'

#main
puyo=0

while True:
    rst=0
    for i in range(12):
        for j in range(6):
            if lst[i][j] != '.':
                rst += bfs(i,j,lst[i][j])

    if rst == 0:
        break
    
    puyo+=1
    drop()
    



print(puyo)

 

 

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview