🔴 문제 개요
🚀 난이도 : GOLD 4
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
제한사항
- 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
- 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
- R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
- 입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.
🟠 Solution
애니팡 형식의 블럭 시뮬레이션 문제입니다. 한 번의 matrix 탐색에서 블럭이 여러번 터지더라도 연쇄를 1회로 측정한다는 것 이외에는 특별한 점이 없어보입니다. matrix의 크기도 매우 작은 12x6로 고정되어있어 무난하게 풀이가 가능할 것 같습니다. 코드의 도입부를 먼저 보겠습니다.
import sys
from collections import deque
from typing import Final
input = sys.stdin.readline
# matrix 크기 고정
ROW: Final = 12
COL: Final = 6
answer = 0
# Puyo 탐색에 활용할 flag, 이전 탐색에서 연쇄가 없었다면 탐색 중단
flag = True
matrix = [list(input().rstrip()) for _ in range(ROW)]연쇄가 몇 번 일어나는 지 측정하기 위해 matrix를 계속 반복해서 순회해야 하는데, 이걸 관리할 변수를 flag로 설정했습니다. 순회가 시작될 때 flag를 False로 설정하고, 연쇄가 1회라도 발생한다면 다시 True로 바꿔주는 방식으로 활용하면 좋을 것 같습니다.
이제 matrix를 순회하면서 4개 이상의 Puyo가 연결되어있는 부분을 찾아야 합니다. 쉽게쉽게 bfs로 이를 탐색하겠습니다. 특정 block과 상, 하, 좌, 우 연결되어있으면서, 해당 block과 같은 블럭이라면 큐에 삽입하는 방식으로 구현하면 됩니다. 이 때 set을 하나 두어서 방문처리 겸, 연결된 block의 수를 세었습니다.
# 상, 하, 좌, 우 탐색
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
while flag:
flag = False
for row in range(ROW):
for col in range(COL):
if matrix[row][col] != ".":
block = matrix[row][col]
queue = deque([(row, col)])
# 터진 puyo를 관리할 set
puyo_set = set()
puyo_set.add((row, col))
# bfs
while queue:
y, x = queue.popleft()
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if (
0 <= ny < ROW
and 0 <= nx < COL
and matrix[ny][nx] == block
and (ny, nx) not in puyo_set
):
queue.append((ny, nx))
puyo_set.add((ny, nx))여기까지 진행되었으면 puyo_set에는 연결된 같은 종류의 블럭의 좌표가 담겨있습니다. 4개 이상이라면 터뜨리면 되겠죠. 이 때 연쇄가 발생한 것이므로 flag를 True로 바꿔주어 다음 순회가 이루어지게 합니다. 여러번 블럭이 터져도 한 번의 순회에 1회만 카운트 된다는 점을 고려하여 flag가 False -> True로 바뀔 때만 정답 카운트를 측정했습니다.
# 4개 이상 상, 하, 좌, 우 연결되었다면
if len(puyo_set) >= 4:
# 터뜨리기
for y, x in puyo_set:
matrix[y][x] = "."
# 연쇄 발생했으므로 이 다음도 탐색
if not flag:
flag = True
# 연쇄 1회 발생
answer += 1이제 빈 공간을 메꿔주어야 합니다. 블럭을 아래로 당기는 방법으로 구현했습니다. 이러한 구현은 여러 문제에서 요긴하게 자주 쓰이는 방법이니 익숙해지면 좋을 것 같습니다.
# 블럭 아래로 당기기
for col in range(COL):
for row in range(ROW - 1, -1, -1):
r, c = row, col
while r + 1 < ROW and matrix[r + 1][c] == ".":
r += 1
matrix[r][c], matrix[row][col] = matrix[row][col], matrix[r][c]
print(answer)마지막으로 정답을 출력하고 코드 작성을 마쳤습니다.
그래프 탐색을 실생활 문제에 접목시켜 유연하게 활용할 수 있는가에 대한 문제였던 것 같습니다. 이번 문제처럼 12x6으로 고정된 작은 matrix라면 매 순회마다 BFS 등 그래프 탐색을 수행해도 무난하게 해결할 수 있겠지만, matrix의 크기가 더 커진다면 더 효율적인 방법을 고려할 수 있어야겠습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
