[ 2933 ] [ 구현 ] 미네랄

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

2933번: 미네랄

 

풀이 과정

---

1. 입력받은 순서대로 미네랄을 하나 없애준다. 이 때 왼쪽, 오른쪽 순으로 없애는 것에 유의
2. 각각의 미네랄을 기준으로 bfs를 진행해서 블록들을 구해준다.
   1. 이 때, 블록이 바닥에 닿지 않는다면, 해당 블록을 이동시켜주어야 하니 잠시 저장시켜 둔다.
3. 바닥에 닿지 않는 블록이 있는 경우, 바닥에 닿지 않는 블록들을 몇칸 내려야 다른 블록에 충돌하는지 벽에 닿는지 검사하고, 해당 칸수만큼 블록 내 모든 미네랄들을 내려준다.
4. 1-3번 과정을 반복한다.

---

소스 코드

---

 

import sys
from collections import deque
import copy

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]

N = int(input())
throws = map(int, input().split())

def bfs(matrix, sx, sy):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    block = [[sx, sy]]
    queue = deque([[sx, sy]])
    matrix[sx][sy] = '.'
    down = False if sx == R-1 else True
    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx, ny = sx + dx[i], sy + dy[i]
            if nx >= 0 and nx < R and ny >= 0 and ny < C and \
               matrix[nx][ny] == 'x':
                down = False if nx == R-1 else down
                block.append([nx, ny])
                queue.append([nx, ny])
                matrix[nx][ny] = '.'

    return block, down
    

def movedown(matrix, block):
    for x, y in block:
        matrix[x][y] = '.'
    movement_count = 0
    # 몇칸 이동해야하는지 구함
    for i in range(1, R):
        for x, y in block:
            if x+i+1 == R or matrix[x+i+1][y] == 'x':
                movement_count = i
                break
        if movement_count != 0:
            break

    for x, y in block:
        matrix[x+movement_count][y] = 'x'
    

def check(matrix):
    target = None
    cp_matrix = copy.deepcopy(matrix)
    for i in range(len(cp_matrix)):
        for j in range(len(cp_matrix[0])):
            if cp_matrix[i][j] == 'x':
                block, down = bfs(cp_matrix, i, j)
                if down:
                    target = block
                    break
        if target:
            break

    if target:
        movedown(matrix, target)

left = True
for throw in throws:
    if left:
        for j in range(C):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    else:
        for j in range(C-1, -1, -1):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    check(matrix)
    left = not left

for m in matrix:
    print("".join(m))