[Gold IV] Puyo Puyo - 11559

문제 링크

성능 요약

메모리: 35036 KB, 시간: 60 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색

문제 설명

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

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

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

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

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

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

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

입력

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

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

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

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

출력

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

---

문제 풀이

문제 분석

문제는 2D 필드에서 뿌요뿌요 게임의 연쇄 횟수를 계산하는 것입니다. 필드는 12x6 크기이며, 각 칸은 비어있거나(.) 특정 색깔(R, G, B, P, Y)의 뿌요로 채워져 있습니다. 같은 색깔의 뿌요가 4개 이상 상하좌우로 연결되면 터지고, 터진 후 위에 있는 뿌요들이 아래로 떨어집니다. 이 과정을 반복하면서 연쇄가 몇 번 일어나는지 계산해야 합니다. 입력은 12줄의 문자열로 표현된 필드 정보이고, 출력은 연쇄 횟수입니다.

접근 방법

이 문제는 시뮬레이션 및 그래프 탐색(BFS) 알고리즘을 사용하여 해결할 수 있습니다.

1. BFS (너비 우선 탐색): 각 뿌요에 대해 BFS를 수행하여 연결된 같은 색깔의 뿌요 그룹을 찾습니다.
2. 뿌요 터뜨리기: 연결된 뿌요가 4개 이상이면 해당 뿌요들을 터뜨립니다 (빈 칸으로 만듭니다).
3. 뿌요 내리기: 터진 뿌요로 인해 생긴 빈 공간을 메우기 위해 위에 있는 뿌요들을 아래로 내립니다.
4. 반복: 뿌요가 터질 수 없을 때까지 1~3단계를 반복하고, 반복 횟수가 연쇄 횟수가 됩니다.

구현 설명

1. 입력 및 초기 설정

• graph 변수에 필드 정보를 저장합니다.
• can_queue 리스트는 탐색 시작점이 될 수 있는 뿌요들의 좌표를 저장합니다. 처음 시작 시 모든 뿌요의 위치가 저장되고, 이후 탐색 과정에서 방문 여부를 체크하여 중복 탐색을 피합니다.
• directions는 상하좌우 이동을 위한 델타 값입니다.

2. BFS 함수 (BFS(i, j, visited))

• visited 2차원 배열을 사용하여 방문 여부를 추적합니다.
• 큐를 사용하여 BFS를 수행하며, history 리스트에 연결된 뿌요의 좌표를 저장합니다.
• 만약 history의 길이가 4 이상이면 (4개 이상의 뿌요가 연결되었다면), 해당 뿌요들을 터뜨립니다 (빈 칸으로 변경합니다).
• 터뜨렸으면 True를, 아니면 False를 반환합니다.

3. 뿌요 내리기 함수 (move(graph))

• 각 열(column)에 대해 아래에서 위로 탐색하면서 뿌요들을 스택에 넣습니다.
• 스택에 있는 뿌요들을 다시 아래에서 위로 꺼내면서 필드를 채웁니다. 스택에 남은 뿌요가 없으면 빈 칸으로 채웁니다.
• 중력에 의해 뿌요가 아래로 이동하는 로직을 구현합니다.

4. 메인 로직

• answer 변수를 사용하여 연쇄 횟수를 저장합니다.
• while True 루프를 사용하여 연쇄가 발생할 때까지 반복합니다.
• 각 반복마다 is_puyo 변수를 False로 초기화합니다. 이 변수는 이번 루프에서 뿌요가 터졌는지 여부를 나타냅니다.
• visited 배열을 초기화합니다.
• can_queue 에 있는 좌표들을 순회하며 BFS 함수를 호출합니다. BFS 함수가 True를 반환하면 is_puyo를 True로 설정합니다.
• is_puyo가 False이면 (더 이상 터질 뿌요가 없으면), answer를 출력하고 루프를 종료합니다.
• move 함수를 호출하여 뿌요를 내립니다.
• answer를 1 증가시킵니다.

⏱복잡도 분석

• 시간 복잡도:
  • BFS는 최악의 경우 모든 칸을 방문하므로 O(12 * 6) = O(1) 입니다 (상수).
  • move 함수는 O(12 * 6) = O(1) 입니다 (상수).
  • 전체 연쇄 횟수는 최악의 경우에도 제한적이므로 전체 시간 복잡도는 O(연쇄 횟수)입니다. 문제에서 연쇄 횟수에 대한 제한이 없지만, 실제로는 작은 상수 값으로 제한되므로 사실상 O(1)에 가깝습니다.
  • 따라서 전체 시간 복잡도는 O(1) (상수 시간)이라고 볼 수 있습니다.
• 공간 복잡도:
  • graph: O(12 * 6) = O(1) (상수)
  • visited: O(12 * 6) = O(1) (상수)
  • queue (BFS): 최악의 경우 모든 칸이 큐에 들어갈 수 있으므로 O(12 * 6) = O(1) (상수)
  • history (BFS): O(12 * 6) = O(1) (상수)
  • 따라서 전체 공간 복잡도는 O(1) (상수 공간)입니다.

핵심 포인트

1. BFS를 활용한 뿌요 그룹 찾기: 같은 색깔의 뿌요가 연결되어 있는지 확인하고, 연결된 그룹의 크기를 파악하는 데 BFS를 효과적으로 사용합니다.
2. 구현의 정확성: 뿌요가 터지고 내려오는 과정을 정확하게 구현하는 것이 중요합니다. move 함수의 로직이 핵심입니다.
3. 방문 처리: 이미 방문한 뿌요를 다시 탐색하지 않도록 visited 배열을 사용하여 중복 탐색을 방지합니다. 이는 시간 효율성을 높이는 데 필수적입니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

graph = []
for i in range(12):
    graph.append(list(input().strip()))

can_queue = []
for i in range(12):
    for j in range(6):
        if graph[i][j] != ".":
            can_queue.append((i,j))

directions = [(1,0),(-1,0),(0,1),(0,-1)]
def BFS(i,j,visited):
    visited[i][j] = True
    queue = deque([(i,j)])
    history = [(i,j)]
    while queue:
        x,y = queue.popleft()
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<12 and 0<=sy<6 and not visited[sx][sy] and graph[sx][sy] == graph[x][y]:
                queue.append((sx,sy))
                visited[sx][sy] = True
                history.append((sx,sy))

    if len(history) >= 4:
        for x,y in history:
            graph[x][y] = "."
        return True

    return False

def move(graph):
    for j in range(6):
        stack = []
        for i in range(11, -1, -1):
            if graph[i][j] != ".":
                stack.append(graph[i][j])
        for i in range(11, -1, -1):
            if stack:
                graph[i][j] = stack.pop(0)
            else:
                graph[i][j] = "."
    return graph

answer = 0
while True:
    is_puyo = False
    visited = [[False] * 6 for i in range(12)]
    for x,y in can_queue:
        if not visited[x][y] and graph[x][y] != ".":
            if BFS(x,y,visited):
                is_puyo = True
    
    if not is_puyo:
        print(answer)
        break

    graph = move(graph)
    answer += 1