[골드5] 11559번 : Puyo Puyo

🛠 문제

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

👩🏻‍💻 해결 방법

필드를 처음부터 확인하며 "."이 아닐 경우, 방문처리를 해주고 bfs() 함수를 실행하였다
bfs 함수 안에서 연결된 뿌요를 chain 리스트에 저장해주고, bfs 함수에서 나온 뒤 해당 리스트의 개수가 4 이상이면 isTrue에 True를 대입하여 연쇄 가능을 나타내고, 연쇄 처리를 해주었다
그리고 down() 함수를 호출해 뿌요를 아래로 떨어지게 만들고, result+1로 연쇄 횟수를 추가해주었다
만약 isTrue가 False라면 연쇄가 불가능하므로 break를 해주었다

소스 코드

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(i, j, ch):
  q = deque()
  q.append((i, j))
  chain.append([i, j])

  while q:
    x, y = q.popleft()
    for k in range(4):
      nx = x + dx[k]
      ny = y + dy[k]

      if 0 <= nx < 12 and 0 <= ny < 6 and visit[nx][ny] == 0 and field[nx][ny] == ch:
        visit[nx][ny] = 1
        chain.append([nx, ny])
        q.append((nx, ny))
      
def down():
  for i in range(6):
    for j in range(10, -1, -1):
      for k in range(11, j, -1):
        if field[j][i] != '.' and field[k][i] == '.':
          field[k][i] = field[j][i]
          field[j][i] = '.'
          break
  
field = [list(input().strip()) for _ in range(12)]

result = 0
while True:
  visit = [[0] * 6 for _ in range(12)]
  isTrue = False

  for i in range(12):
    for j in range(6):
      if field[i][j] != '.' and visit[i][j] == 0:
        visit[i][j] = 1
        chain = []
        bfs(i, j, field[i][j])
        if len(chain) >= 4:
          isTrue = True
          for x, y in chain:
            field[x][y] = '.'
  
  if not isTrue: break
  down()
  result += 1

print(result)