[백준/Python] 11559번(BFS)_Puyo Puyo

📌문제 유형

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, BFS (골드 Lv.4)

 

📌문제

11559번: Puyo Puyo

 

📌나의 문제풀이

from collections import deque

maps = []
for _ in range(12):
    maps.append(list(map(str,input())))

ans_list = [0]
result = 0
while True:
    visited = [[0 for _ in range(6)] for _ in range(12)]
    check = []  # 4개 이상이라 터지는 경우 좌표값 저장
    # maps 한 번 다 돌기 
    for x in range(12):
        for y in range(6):
            if maps[x][y] != '.':
                target = maps[x][y]
                cnt = 1

                res = [(x,y)]
                q = deque([])
                q.append((x,y))
                visited[x][y] = 1

                while q:
                    x_, y_ = q.popleft()
                    dx = [0,0,1,-1]
                    dy = [1,-1,0,0]

                    for i in range(4):
                        nx = x_ + dx[i]
                        ny = y_ + dy[i]
                        if 0 <= nx < 12 and 0 <= ny < 6:
                            if maps[nx][ny] == target and visited[nx][ny] == 0:
                                cnt += 1
                                visited[nx][ny] = 1
                                q.append((nx,ny))
                                res.append((nx,ny))
                if cnt >= 4:    # 4개 이상인 경우만 저장
                    check.extend(res)

    # 터진거 .으로 만들어야 함
    for k in range(len(check)):
        maps[check[k][0]][check[k][1]] = '.'
    result += 1

    # 위에 있는 알파벳 아래로 내리기
    new = []
    for yu in range(6):
        tmp = []
        for xu in range(12):
            if maps[xu][yu] != '.':
                tmp.append(maps[xu][yu])
        new_list = ['.' for _ in range(12-len(tmp))]
        new_list.extend(tmp)
        new.append(new_list)
    maps = list(map(list,zip(*new)))    # 행렬 transpose


    if check == []: # check 비어있으면 터지는 것 없으므로 종료
        break
    else:
        ans_list.append(result)

print(ans_list[-1])

 

📌 다른사람의 문제풀이

- 함수 한개씩 만들어서 작성

[백준] 11559(파이썬) - Puyo Puyo

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

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

dx = [1,-1,0,0]
dy = [0,0,1,-1]

# 아래로 당기는 함수하나
def down():
    for i in range(6):
        for j in range(10, -1, -1):
            for k in range(11, j, -1):
                if data[j][i] != "." and data[k][i] == ".":
                    data[k][i] = data[j][i]
                    data[j][i] = "."
                    break
                           

# 4칸 확인하는 함수 하나
def bfs(x,y):
    q = deque()
    q.append((x,y))
    temp.append((x,y))
    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0<= nx < 12 and 0<= ny < 6 and data[nx][ny] == data[x][y] and visited[nx][ny] == 0:
                q.append((nx,ny))
                temp.append((nx,ny))
                visited[nx][ny] = 1

# 4칸이상일 때 지우는 함수하나
def delete(temp):
    for a,b in temp:
        data[a][b] = "."

# def show(data):
#     for i in range(12):
#         print(data[i],end="\n")

ans = 0
while 1:
    flag = 0
    visited = [[0]*6 for _ in range(12)]
    for i in range(12):
        for j in range(6):
            if data[i][j] != '.' and visited[i][j] == 0:
                visited[i][j] = 1
                temp = []
                bfs(i,j)
                # 4칸확인
                if len(temp) >= 4:
                    flag = 1
                    delete(temp)
    if flag == 0:
        break
    down()
    ans += 1

print(ans)

 

📌 리뷰

- 조건 조심하기

• 같은 색 뿌요가 4개 이상일때 터짐 - 4개로 한정지어서 틀렸음
• 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가 - 한 그룹당 연쇄 한 번으로 지정해서 틀렸음