[백준] 2933번 미네랄 (파이썬)

난이도 : GOLD II

문제링크 : https://www.acmicpc.net/problem/2933

문제해결 아이디어

• 화살을 쏜다 left, right 번갈아가면서
• 없어진 미네랄의 상,하,좌,우에 미네랄이 있으면 dq에 넣는다.(클러스터)
• q(클러스터)를 탐색하면서 만약 바닥에 닿은경우는 패스, 공중에 떠있는 경우중 열(세로)의 맨 밑은 공중에 떠있는 경우 이므로 옮겨야한다
• 미네랄에 닿거나 바닥에 닿을때까지 한칸씩 내린다. 이때 ㄷ 자 모양 주의 해야함.

소스코드

from collections import deque, defaultdict, Counter
import sys

input = sys.stdin.readline

n,m = map(int,input().split())

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

board = []

for _ in range(n):
    board.append(list(input().strip()))

def shoot(d,l):
    line = n - l
    if 'x' in board[line]:
        if d == 0:
            seq = board[line].index('x')
            board[line][seq] = '.'
        else:
            seq = list(reversed(board[line])).index('x')
            seq = m-seq-1
            board[line][seq] = '.'


        for i in range(4):
            nl = line + dx[i]
            ns = seq + dy[i]

            if 0 <= nl < n and 0 <= ns < m and board[nl][ns] == 'x':
                dq.append((nl, ns))


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

    move(check, fall_list)

def move(visited,fall):
    dis = 1
    while True:
        flag = False
        for x, y in fall:
            if x + dis == n:
                flag = True
                break
            if board[x + dis][y] == 'x' and not visited[x + dis][y]:
                flag = True
                break
        if flag:
            break
        dis += 1
    dis -= 1
    for i in range(n - 2, -1, -1):
        for j in range(m):
            if visited[i][j] and board[i][j] == 'x':
                board[i + dis][j] = 'x'
                board[i][j] = '.'
k = int(input())

lane = list(map(int, input().split()))

dq = deque()

for i in range(k):
    l = lane.pop(0)
    shoot(i%2, l)
    while dq:
        x,y = dq.popleft()
        bfs(x,y)

for i in range(n):
    print(''.join(board[i]))