백준 2933 미네랄

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

구현 + bfs문제였다.
이 문제의 핵심은 어떤 미네랄을 파괴하였을때, 클러스터가 분리되는 지점이 발생하는데 이 클러스터를 내리는 것을 구현하는 것이 핵심이다.

깬 지점을 중심으로 주변 4칸에 있을 수 있는 미네랄은 분리되어 내려와야 하는 클러스터일 가능성이 있기때문에 이를 확인해 큐에 넣어준다.

바닥에 닿지 않는 클러스터라면 클러스터를 바닥까지 내려야 하는데, 클러스터의 미네랄을 하나씩 내려보면서 바닥이 아니면서, 같은 클러스터가 아닌 미네랄을 만날때 까지 내려주고, 클러스터의 어떤 한 미네랄도 부딛히게 된다면 이를 종료해준다.

from collections import deque
r,c = map(int,input().split())
arr = []
for i in range(r):
    arr.append(list(input()))
n = int(input())
heights = list(map(int,input().split()))
turn = 1 ## 왼쪽턴
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def move(cluster,visited):
    cnt = 1; t = 0
    while True:
        for mineral in cluster:
            mx,my = mineral
            if mx + cnt == r-1:
                t = 1
                break
            if arr[mx+cnt+1][my] == 'x' and not visited[mx+cnt+1][my]:
                t = 1
                break
        if t:
            break
        cnt += 1
    for i in range(r-2,-1,-1):
        for j in range(c):
            if arr[i][j] == 'x' and visited[i][j]:
                arr[i][j] = '.'
                arr[i+cnt][j] = 'x'
def bfs(x,y):
    visited = [[0 for i in range(c)] for i in range(r)]
    cluster = []
    if arr[x][y] != 'x':
        return
    queue = deque([(x,y)])
    while queue:
        x,y = queue.popleft()
        cluster.append((x,y))
        if x == r-1:
            return
        visited[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny] and arr[nx][ny] == 'x':
                visited[nx][ny] = 1
                queue.append((nx,ny))
    move(cluster,visited)

for h in heights:
    queue = deque([])
    if turn:
        for i in range(c):
            if arr[r-h][i] == 'x':
                arr[r-h][i] = '.'
                for k in range(4):
                    nx = r-h + dx[k]
                    ny = i + dy[k]
                    if 0 <= nx < r and 0 <= ny < c:
                        queue.append((nx,ny))
                break
        turn = 0
    else:
        for i in range(c-1,-1,-1):
            if arr[r-h][i] == 'x':
                arr[r-h][i] = '.'
                for k in range(4):
                    nx = r-h + dx[k]
                    ny = i + dy[k]
                    if 0 <= nx < r and 0 <= ny < c:
                        queue.append((nx,ny))
                break
        turn = 1
    while queue:
        x,y = queue.popleft()
        bfs(x,y)
for row in arr:
    print(''.join(row))