[BOJ] 2933 - 미네랄 (Python)

 

 

아이디어

 

막대기를 맞아 미네랄이 파괴된 칸을 기준으로 주변을 BFS하여 바닥에 닿아 있지 않은 클러스터들을 이동시킨다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():

    def throw(i, j):
        visited = [[0]*C for _ in range(R)]
        for di, dj in delta:
            ni, nj = i+di, j+dj
            if R > ni >= 0 and C > nj >= 0:
                if board[ni][nj] == 'x' and visited[ni][nj] == 0:
                    visited[ni][nj] = 1
                    bottom = [-1]*C
                    queue = [(ni, nj)]
                    idx = 0
                    cnt = 1
                    while idx < cnt:
                        r, c = queue[idx]
                        idx += 1
                        if r > bottom[c]:
                            bottom[c] = r
                        for dr, dc in delta:
                            nr, nc = r+dr, c+dc
                            if R > nr >= 0 and C > nc >= 0:
                                if board[nr][nc] == 'x' and visited[nr][nc] == 0:
                                    visited[nr][nc] = 1
                                    queue.append((nr, nc))
                                    cnt += 1
                    d = 0
                    for dr in range(1, R-max(bottom)):
                        for c in range(C):
                            if bottom[c] >= 0:
                                r = bottom[c]
                                if board[r+dr][c] == 'x':
                                    break
                        else:
                            d = dr
                            continue
                        break
                    if d > 0:
                        for r, c in queue:
                            board[r][c] = '.'
                        for r, c in queue:
                            board[r+d][c] = 'x'

    R, C = map(int, input().split())
    board = [[*input().rstrip()] for _ in range(R)]
    N = int(input())
    H = tuple(map(int, input().split()))
    for n in range(N):
        i = R-H[n]
        if n%2:
            for j in range(C-1, -1, -1):
                if board[i][j] == 'x':
                    board[i][j] = '.'
                    throw(i, j)
                    break
        else:
            for j in range(C):
                if board[i][j] == 'x':
                    board[i][j] = '.'
                    throw(i, j)
                    break
    for i in range(R):
        print(''.join(board[i]))

solution()