[python] 백준 > BFS > Puyo Puyo(11559)

[문제]

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

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

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

입력

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없e다.

출력

현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.

 

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

[풀이]

from collections import deque

# BFS 함수
def bfs(x, y):
    queue = deque()
    temp = set()
    queue.append((x, y))

    while queue:
        qx, qy = queue.popleft()
        if (qx, qy) in temp:
            continue
        temp.add((qx, qy))
        for i in range(4):
            sx, sy = qx+dx[i], qy+dy[i]
            if not(0<=sx<n and 0<=sy<m):
                continue
            if arr[qx][qy] == arr[sx][sy]:
                queue.append((sx, sy))
    return temp

# 떨어뜨리는 함수
def fall():
    for i in range(n-1, -1, -1):
        for j in range(m):
            if arr[i][j] == '.':
                for s in range(i-1, -1, -1):
                    if arr[s][j] != '.':
                        arr[i][j] = arr[s][j]
                        arr[s][j] = '.'
                        break


# 메인 함수
if __name__ == '__main__':
    answer = 0
    n, m = 12, 6
    arr = list(list(input()) for _  in range(12))
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    
    while True:
        check = 0
        for i in range(n):
            for j in range(m):
                if arr[i][j]=='.': continue
                result = bfs(i, j)
                if len(result) >= 4:
                    if check == 0: 
                        check = 1
                    for x, y in result:
                        arr[x][y] = '.'
        fall()
        if check == 1:  
            answer += 1
        else:
            break
    print(answer)

• visited list대신 temp라는 set을 사용해 이미 방문했던 것인지 확인한다.
• bfs함수에서 temp set에 어떤 좌표들을 거쳤는지(같은 알파벳이 있는 좌표) 담아서 리턴한다.
• 그 리턴값의 갯수가 4개 이상일 경우check를 1로 바꿔준다.(터트릴게 있다는 뜻)
• 한 구역만 터지는게 아니라 다른구역에도 동시에 터질게 있을경우 한번에 터지고 +1이 돼야 하기 때문에 while문을 사용해 2차원 배열을 다 돈 뒤에 fall() 함수를 호출하고, answer에 +1을 해준다.

 

[다른 사람의 풀이]

import sys
from collections import deque
graph = [list(sys.stdin.readline().strip()) for _ in range(12)]
def drop(graph):
    for i in range(6):
        k = 11
        for j in range(11,-1,-1):
            if graph[j][i]!='.':
                if k!=j:
                    graph[k][i] = graph[j][i]
                    graph[j][i] = '.'
                k -= 1
dx , dy = [0,0,1,-1], [1,-1,0,0]
def bfs(start):
    dq, check = deque(), set()
    dq.append(start)
    y, x, c = start
    check.add((y,x))
    while dq:
        y, x, c = dq.popleft()
        for k in range(4):
            b, a = y+dy[k], x+dx[k]
            if (0<=b<=11) and (0<=a<=5) and (graph[b][a]==c) and ((b,a) not in check):
                check.add((b,a))
                dq.append((b,a,c))
    if len(check) > 3:
        for (y,x) in check:
            graph[y][x]='.'
        return 1
    return 0
count = 0
while True:
    tmp = 0
    for i in range(12):
        for j in range(6):
            if graph[i][j]!='.':
                tmp += bfs((i,j ,graph[i][j]))
    if tmp:
        count += 1
    else:
        print(count)
        break
    drop(graph)

• check를 활용해 4개이상으로 뭉쳐있나 체크했고 터트렸다.
• drop 함수를 따로 만들어 뿌요를 바닥으로 내려 정리해줬다.
• bfs Input으로 뿌요색도 함께 넣어줬다.
• bfs에 return 값을 줘서 터졌는지 확인했고 한번이라도 터졌으면 count+=1 해줬고 한번도 안 터지면 게임을 끝냈다.