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

🥚문제

---

🥚입력/출력

---

🍳코드

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

arr = [list(input().strip()) for _ in range(12)]
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def bfs(r, c, visited):
    q = deque([(r, c)])
    visited[r][c] = True
    tmp_puyo = [(r, c)]

    while q:
        r, c = q.popleft()
        color = arr[r][c]

        for move in moves:
            new_r = r + move[0]
            new_c = c + move[1]
            if 0 <= new_r < 12 and 0 <= new_c < 6:
                if not visited[new_r][new_c]:
                    if arr[new_r][new_c] == color:
                        visited[new_r][new_c] = True
                        q.append((new_r, new_c))
                        tmp_puyo.append((new_r, new_c))

    return tmp_puyo


def move_puyos(puyos):
    # 터지는 뿌요가 있는 칸을 빈칸으로 만듦
    for puyo in puyos:
        arr[puyo[0]][puyo[1]] = "."

    # 맨 아래 row부터 위로 탐색해가야 함
    for r in range(11, -1, -1):
        for c in range(6):
            if arr[r][c] != '.':
                new_r = r
                while 0 <= new_r + 1 < 12:
                    if arr[new_r+1][c] == '.':
                        new_r += 1
                    else:
                        break
                if r < new_r:
                    arr[new_r][c] = arr[r][c]
                    arr[r][c] = '.'


# 연쇄 카운트
cnt = 0
visited = [[False]*6 for _ in range(12)]
puyos = []  # 이번 턴에 터지는 뿌요들의 위치를 저장한다

# while loop 한 번 돌면 = 한 턴
while True:
    for r in range(12):
        for c in range(6):
            if arr[r][c] != '.' and not visited[r][c]:
                tmp_puyo = bfs(r, c, visited)
                if len(tmp_puyo) >= 4:
                	# tmp_puyo가 4개 이상이면 puyos에 추가
                    puyos += tmp_puyo

    # 터질 수 있는 뿌요가 하나도 없으면 while 중단
    if len(puyos) == 0:
        break
	
    # 뿌요가 4개 이상이면 터질 수 있음
    if len(puyos) >= 4:
        # 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
        # 연쇄 카운트 + 1
        cnt += 1
        # 뿌요들이 내려옴
        move_puyos(puyos)

    # visited 초기화
    visited = [[False]*6 for _ in range(12)]
    # puyos 초기화
    puyos = []


print(cnt)

---

🧂아이디어

구현, 탐색

• 한 턴을 4개 이상 연결된 뿌요들이 터지고, 남은 뿌요들이 아래로 떨어지는 것까지로 보기로 한다.

• 4개 이상 연결된 뿌요들을 터뜨리기
  • 같은 색 뿌요가 상하좌우로 4개 이상 연결되어 있는지 bfs로 확인한다.
  • 이때, 문제에서 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 ✨여러 그룹이 터지더라도 한번의 연쇄✨가 추가된다. 라는 말이 있기 때문에 전체 arr를 탐색하면서 4개 이상 연결되어 있는 그룹을 모두 구해야 한다.
  • bfs의 결과, 연결된 뿌요들이 상하좌우로 4개 이상이라면, 연결되어 있는 뿌요들의 좌표를 puyos라는 리스트에 추가한다.
  • puyos의 길이가 0이라면, 더이상 터뜨릴 뿌요가 없다는 것이므로 whlie loop를 빠져나온다.
  • puyos의 길이가 4 이상이라면 이번 턴에 뿌요가 한 그룹 이상 터진다는 이야기이므로 연쇄 카운트를 증가시키고, 남은 뿌요들을 아래로 떨어뜨리는 move_puyos 함수를 호출한다.

• 남은 뿌요들을 아래로 떨어뜨리기 (move_puyos)
  • puyos에 저장된 좌표를 puyo라고 할 때, arr[puyo[0]][puyo[1]] 을 '.'(빈칸)으로 만든다.
  • 이후, 아래쪽에 있는 행부터 위로 올라오면서 (r = 11, 10, ... , 1, 0 순서로) arr[r][c]가 '.'(빈칸)이 아니라 뿌요가 위치해 있다면, arr[r+1][c], arr[r+2][c], arr[r+3][c]... 를 하면서 움직일 수 있는 가장 아래에 있는 빈칸인 arr[new_r][c]에 현재 뿌요를 이동시키고, arr[r][c]는 빈칸으로 만든다.

• 이번 턴을 마무리 하면서, visited와 puyos를 초기화한다.