BOJ 2933 미네랄 python

막대기를 던진 줄을 차례대로 for문을 돌면서, 미네랄이 있으면 지우고, 없으면 continue
미네랄 주위 4칸 dfs, 바닥을 만나면 ans.append(1)을 해주고 ans != 0이면 continue
ans == 0이면 각 열을 돌면서 떨어질 수 있는 값을 moved에 저장, 아래부터 미네랄을 옮김

알고리즘 자체는 간단한 dfs인데, 구현이 까다로운 문제였다. 미리 마지막 줄을 미네랄로 채워주면, 따로 예외처리를 안해도 된다.

풀이 코드

import sys
sys.setrecursionlimit(10**6)
rl = sys.stdin.readline
r, c = map(int, rl().split())
 
g = [list(rl().rstrip()) for _ in range(r)]
g.append(["x"]*c)
n = int(rl())
qr = [r-i for i in list(map(int, rl().split()))]
dr = [(1,0),(-1,0),(0,1),(0,-1)]
 
def dfs(x, y):
    if y == r: out.append(1)
    if dp[y][x] == 0:
        dp[y][x] = 1
        for dx, dy in dr:
            if not (0<=x+dx<c and 0<=y+dy<r+1): continue
            if dp[y+dy][x+dx]: continue
            if g[y+dy][x+dx] == 'x': dfs(x+dx,y+dy)
 
rlch = 1
for y in qr:
    if rlch: x = ''.join(g[y]).find('x')
    else: x = c-1-''.join(reversed(g[y])).find('x')
    if x == -1 or x == c:
        rlch = (rlch+1)%2
        continue
    g[y][x] = '.'
    for dx, dy in dr:
        if not (0<=x+dx<c and 0<=y+dy<r+1): continue
        if g[y+dy][x+dx] == '.': continue
        out = []
        dp = [[0 for _ in range(c)] for _ in range(r+1)]
        dfs(x+dx,y+dy)
        if not out:
            moved = r
            for chx in range(c):
                chy, nowy = 0, -200
                while chy <= r:
                    if dp[chy][chx]: nowy = chy
                    elif g[chy][chx] == 'x': moved = min(moved, chy-nowy-1) 
                    chy += 1
            for i in range(r, -1, -1):
                for j in range(c):
                    if dp[i][j] == 0: continue
                    g[i][j] = '.'
                    g[i+moved][j] = 'x'
            break
    rlch = (rlch+1)%2
 
for i, gg in enumerate(g):
    if i != r: print(''.join(gg))