백준 2933 미네랄 (파이썬)

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

2933번: 미네랄

1. 막대를 좌우 순서대로 던질 수 있도록 변수를 설정한다 (1, -1 반복)

2. 미네랄을 파괴했다면 상하좌우에 미네랄이 있는지 확인한다. 있다면 떨어질 수 있는 후보이므로 저장해둔다

3. 큐에서 하나씩 꺼내서 bfs를 돌려본다.

   이동하면서 아래 칸이 . 이면 떨어질 수 있는 클러스터의 맨 아래이므로 저장해둔다

   만약 바닥까지 도착하면 떨어지지 않으므로 return한다

   바닥에 도착하지 않으면 떨어져야 하므로 떨어지는 작업을 수행한다

4. fall 함수는 클러스터가 얼마만큼 떨어져야하는지 확인한 후 클러스터를 밑에서부터 순차적으로 떨어뜨린다

5. 모든 작업을 완료한 후 동굴에 대한 리스트를 출력한다

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def destroy(i, left):
    i, j = r - i, 0
    if left == 1:
        for k in range(c):
            if a[i][k] == 'x':
                a[i][k] = '.'
                j = k
                break
    else:
        for k in range(c-1, -1, -1):
            if a[i][k] == 'x':
                a[i][k] = '.'
                j = k
                break

    for k in range(4):
        ni = i + dx[k]
        nj = j + dy[k]
        if 0 <= ni < r and 0 <= nj < c:
            if a[ni][nj] == 'x':
                dq.append([ni, nj])

def bfs(x, y):
    q = deque()
    check = [[0]*c for _ in range(r)]
    fall_list = []
    q.append([x, y])
    check[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == r-1:
            return
        if a[x+1][y] == '.':
            fall_list.append([x, y])
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if a[nx][ny] == 'x' and not check[nx][ny]:
                    check[nx][ny] = 1
                    q.append([nx, ny])

    fall(check, fall_list)

def fall(check, fall_list):
    k, flag = 1, 0
    while True:
        for i, j in fall_list:
            if i + k == r-1:
                flag = 1
                break
            if a[i+k+1][j] == 'x' and not check[i+k+1][j]:
                flag = 1
                break
        if flag:
            break
        k += 1

    for i in range(r-2, -1, -1):
        for j in range(c):
            if a[i][j] == 'x' and check[i][j]:
                a[i][j] = '.'
                a[i+k][j] = 'x'

r, c = map(int, input().split())
a = [list(input().strip()) for _ in range(r)]
n = int(input())
s = list(map(int, input().split()))
dq = deque()

left = 1
while n:
    index = s.pop(0)
    destroy(index, left)

    while dq:
        x, y = dq.popleft()
        bfs(x, y)

    left *= -1
    n -= 1

for i in range(r):
    for j in range(c):
        print(a[i][j], end='')
    print()