[백준] 11559번 Puyo Puyo(python 파이썬)

저번 프로그래머스 데브매칭에서 BFS&DFS 개념이 부족하다는 것을 깨닫고

백준 문제집에 있는 전부 풀어봤습니다.

 

 

제가 작성한 코드 답

https://github.com/21CatchStudy/Jinho_repo/tree/main/dfs%26bfs/baekjoon

GitHub - 21CatchStudy/Jinho_repo

 

 

 

 

11559번 Puyo Puyo [Python]

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

11559번: Puyo Puyo

요구 알고리즘 : DFS&BFS

생각해보아야 할 것

1. 같은 색깔의 개수를 어떻게 체크하여야 할까?

 

bfs 이용하여 체크

• bfs를 이용하여 같은 색깔의 크기가 4이상 될 경우 해당 좌표 리스트(sames) 반환 

def same_check(i,j):
    Q = deque()
    sames = []
    Q.append((i,j,G[i][j]))
    visited[i][j] = True
    sames.append((i,j))
    while Q:
        x,y,color = Q.popleft()
        for dx,dy in zip(X,Y):
            nx,ny = x+dx,y+dy
            if 0<=nx<12 and 0<=ny<6:
                if G[nx][ny] == color and not visited[nx][ny]:
                    visited[nx][ny] = True
                    Q.append((nx,ny,color))
                    sames.append((nx,ny))
    if len(sames)>=4:
        return sames
    return

 

 

2. 동시에 여러색깔이 터지는 것은 어떻게 구현할까?

 

리스트에 추가

• 터져야 하는 블록들을 리스트에 추가

                result = same_check(i,j)
                if result:
                    same_results.extend(result)

 

3. 터지고 내려오는 것은 어떻게 구현할까?

 

정렬 이용

• 터지는 블록부터 천장까지 하나씩 내려와 위에 블록 저장
• 천장은 빈블록('.')로 할당

same_results.sort(key= lambda x: (x[0],x[1]))
for same in same_results:
    x_idx,y_idx = same
    for p in range(x_idx,0,-1):
        G[p][y_idx] = G[p-1][y_idx] 
    G[0][y_idx] = '.'
continue

 

 

 

전체 코드

"""
https://www.acmicpc.net/problem/11559
Puyo Puyo / 골드 4 / 70분
실패 2(틀렸습니다 2 )
"""
import sys
from collections import deque
input = sys.stdin.readline

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

X = [-1,1,0,0]
Y = [0,0,1,-1]

def same_check(i,j):
    Q = deque()
    sames = []
    Q.append((i,j,G[i][j]))
    visited[i][j] = True
    sames.append((i,j))
    while Q:
        x,y,color = Q.popleft()
        for dx,dy in zip(X,Y):
            nx,ny = x+dx,y+dy
            if 0<=nx<12 and 0<=ny<6:
                if G[nx][ny] == color and not visited[nx][ny]:
                    visited[nx][ny] = True
                    Q.append((nx,ny,color))
                    sames.append((nx,ny))
    if len(sames)>=4:
        return sames
    return

ans = 0
while True:
    same_results = []
    visited  = [[False for _ in range(6)] for _ in range(12)]
 
    for i in range(12):
        for j in range(6):
            if G[i][j] !='.' and not visited[i][j]:
                result = same_check(i,j)
                if result:
                    same_results.extend(result)
    if not same_results:
        break
    else:
        ans+=1
        same_results.sort(key= lambda x: (x[0],x[1]))
        for same in same_results:
            x_idx,y_idx = same
            for p in range(x_idx,0,-1):
                G[p][y_idx] = G[p-1][y_idx] 
            G[0][y_idx] = '.'
        continue

print(ans)