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

 

 

문제 링크

 

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

11559번: Puyo Puyo

 

 

 

문제 풀이

 

1) 4개 이상 연속된 뿌요들을 찾아 삭제하는 함수

2) 중력 작용으로 뿌요를 아래로 떨어뜨리는 함수

이렇게 두 가지 함수로 분리하여 작성했습니다.

 

 

1) 4개 이상 연속된 뿌요들을 찾아 삭제하는 함수

 

def burst(i, j, color):
    global flag
    q = deque()
    q.append([i, j])
    visited[i][j] = 1
    puyo = [[i, j]]
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < 12 and 0 <= ny < 6 and graph[nx][ny] == color and not visited[nx][ny]:
                q.append([nx, ny])
                visited[nx][ny] = 1
                puyo.append([nx, ny])
    if len(puyo) >= 4:
        flag = True
        for x, y in puyo:
            graph[x][y] = '.'

 

매개변수로 들어가는 i, j는 시작점의 x, y좌표이며 color는 해당 좌표의 뿌요의 색깔입니다.

메인 함수에서 비어있지 않은, 즉 뿌요가 존재하는 위치에 대해서만 함수를 실행했습니다.

bfs 탐색을 통해 주변의 같은 색깔의 뿌요 좌표를 puyo 배열에 넣고

탐색이 끝난 후 puyo의 길이가 4 이상일 경우 터트려줘야 하므로 값을 '.'으로 바꿔줍니다.

이때, 연쇄작용이 발생했다는 것을 메인 함수에 전달해야 하기 때문에

초기값이 False인 전역 변수 flag의 값을 True로 바꿔줍니다.

메인 함수에서 해당 값이 False가 된다면, 반복된 연쇄작용이 중단된 것이므로

게임을 중단하고 그 동안 발생한 연쇄작용 수를 print해 줄 것입니다.

 

 

2) 중력 작용으로 뿌요를 아래로 떨어뜨리는 함수

 

def fall():
    for y in range(6):
        for x in range(10, -1, -1):
            for fall_point in range(11, x, -1):
                if graph[x][y] != '.' and graph[fall_point][y] == '.':
                    graph[fall_point][y] = graph[x][y]
                    graph[x][y] = '.'

 

 

같은 열에 대해 아래 행에서부터 뿌요를 떨어뜨려야 합니다.

(위부터 떨어뜨릴 경우 아래의 뿌요가 떨어졌을 때

함께 떨어지는 것을 구현하기 위해 로직이 불필요하게 반복됩니다.)

10행부터 체크하여 뿌요가 있을 경우 11행부터 현재 행 위치까지 탐색하여

가장 먼저 비어있는 곳에 뿌요를 위치시키고 기존 좌표의 값은 '.'으로 바꿔줍니다.

 

 

전체 코드

 

from collections import deque

def fall():
    for y in range(6):
        for x in range(10, -1, -1):
            for fall_point in range(11, x, -1):
                if graph[x][y] != '.' and graph[fall_point][y] == '.':
                    graph[fall_point][y] = graph[x][y]
                    graph[x][y] = '.'

def burst(i, j, color):
    global flag
    q = deque()
    q.append([i, j])
    visited[i][j] = 1
    puyo = [[i, j]]
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < 12 and 0 <= ny < 6 and graph[nx][ny] == color and not visited[nx][ny]:
                q.append([nx, ny])
                visited[nx][ny] = 1
                puyo.append([nx, ny])
    if len(puyo) >= 4:
        flag = True
        for x, y in puyo:
            graph[x][y] = '.'

graph = [list(input().rstrip()) for _ in range(12)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
result = 0

while True:
    flag = False
    visited = [[0] * 6 for _ in range(12)]

    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.' and not visited[i][j]:
                burst(i, j, graph[i][j])

    if flag:
        fall()
        result += 1
    else:
        break

print(result)