백준/ Gold 4 문제 , 백준 파이썬 11559 , Puyo Puyo [BFS]

백준/ Gold 4 문제 , 백준 파이썬 11559 , Puyo Puyo [BFS]

 

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
터트리고 칸 내리는 과정이 진짜 Fucking Hell 이였다. 그래도 혼자 해결 성공

 

 

문제 출처

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

11559번: Puyo Puyo

 

 

 

반례

 

RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRGG
RRRRRR
RRRRGG
RRRRRR

 

정답 : 2

 

 

 

......
......
......
......
......
......
......
......
.Y....
RY....
RRYG..
RYYGG.

 

 

정답 : 2

 

 

......
......
......
......
......
......
......
......
......
......
......
......

정답 : 0

 

 

......
......
......
......
......
......
.G....
RR....
RY....
RYG...
RRY...
RYYGG.

정답 : 3

 

 

 

풀이

 

 

1. 기본 세팅

1. 상하좌우

 

2. 12행의 MAP 리스트 입력받기

 

 

2. BFS

 

특별한건 없는 BFS 함수이다. 그냥 인접한게 4개 이상인지 확인하고 맞다면 모두 터트려준다.

 

터트렸다면 True 리턴 아니라면 False 리턴이다.

 

 

3. BFS 호출 및 리스트 재배열 ★

 

터트리는건 쉬운데 이후 밑으로 리스트들을 재 구성하는 것이 진짜 어려웠다.

 

초반에 0행부터 잘못돌려서 다시 짜고 tmp=0 으로 만드는 부분을 j 재할당 이전에 써서 값이 틀리고 등등...

이 부분 코드짜는데 머리에 과부하가 걸렸음.

 

 

밑에서 부터 위로 쭉 확인해가면서 . 위에 문자가 있다면 밑으로 쫙 내려주고 다시 위로 올라가며 확인하는 과정을 거쳐야 한다.

 

 

중요한 점은 초반에 터트릴수 있는건 연쇄작용으로 다 터트려야 하기 때문에 이 부분도 카운트 잘해주자.

 

 

 

 

 

 

 

정답

 

 

 

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

dr=[(1,0),(0,1),(-1,0),(0,-1)]

MAP=[list(input().rstrip()) for _ in range(12)]

def bfs(T,x,y):
    dq=deque()
    dq.append([x,y])
    store=[(x,y)]
    visited=[[0 for _ in range(12)] for _ in range(12)]
    visited[x][y]=1
    cnt=1
    while dq:
        X,Y=dq.popleft()
        for a,b in dr:
            mx,my=X+a,Y+b
            if 0<=mx<12 and 0<=my<6:
                if MAP[mx][my]==T and not visited[mx][my]:
                    store.append((mx,my))
                    cnt+=1
                    dq.append([mx,my])
                    visited[mx][my]=1
    if cnt>=4:
        for n,m in store:
            MAP[n][m]='.'
        return True
    return False

C=0
while True:
    L=[]
    check=False
    for i in range(11,-1,-1):
        for j in range(6):
            if MAP[i][j]!='.':
                result=bfs(MAP[i][j],i,j)
                if result==True:
                    check=True
    for i in range(6):
        tmp=0
        CK=False
        j=11
        while True:
            if MAP[j][i]=='.':
                tmp+=1
                CK=True
                j-=1
            else:
                if CK==True:
                    MAP[j][i],MAP[j+tmp][i]=MAP[j+tmp][i],MAP[j][i]
                    j=j+tmp
                    tmp=0
                    CK=False
                else:
                    j-=1
            if j==-1:
                break
    if check==False:
        print(C)
        break
    C+=1