문제 링크

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

문제 설명

• 맵의 양 옆에서 번갈아가며 특정 높이에서 막대기를 던진다
• 막대기에 맞은 미네랄은 떠있을 경우 떨어진다
• 모든 막대기를 던진 후 맵을 출력

풀이

• 특정 높이에서 만나는 미네랄 구하기
• 있을 경우 상, 하, 좌, 우로 DFS 하여 cluster 및 떠있는지 구하기
• 떠있을 경우 cluster를 떨어트림

DFS 구현

• 가장 아래에 있는 좌표를 한 번이라도 지날 경우 floating = False
• 모든 좌표를 x좌표 별로 최대 힙에 저장

down 함수 구현

• cluster의 각 x좌표 별 최대 힙의 0번째 값과(가장 아래의 y)
• 미네랄 또는 바닥과의 거리를 구한다
• x좌표 별 거리의 최솟값을 구한다
• 최솟값만큼 cluster의 모든 좌표를 내려준다

코드

import sys
import heapq


def init():
    ipt = sys.stdin.readline
    r, c = map(int, ipt().split())
    board = [list(ipt().rstrip()) for _ in range(r)]
    n = int(ipt())
    stick_list = list(map(int, ipt().split()))
    dy = [0, -1, 0, 1]
    dx = [-1, 0, 1, 0]
    return r, c, board, n, stick_list, dy, dx


def get_mineral(start, step):
    y, x = start
    while 0 <= x < c:
        if board[y][x] == 'x':
            return (y, x)
        x += step


def dfs(start):
    global floating
    sy, sx = start
    visited[sy][sx] = True
    if sx not in cluster:
        cluster[sx] = [-sy]
    else:
        heapq.heappush(cluster[sx], -sy)
    if sy == r-1:
        floating = False
    for d in range(4):
        ny = sy + dy[d]
        nx = sx + dx[d]
        if 0 <= ny < r and 0 <= nx < c:
            if board[ny][nx] == 'x' and not visited[ny][nx]:
                dfs((ny, nx))


def get_gap(y, x):
    for i in range(y, r):
        if i+1 == r or board[i+1][x] == 'x':
            return i-y


def get_min_gap():
    min_gap = r
    for x in cluster:
        y = -cluster[x][0]
        gap = get_gap(y, x)
        min_gap = min(min_gap, gap)
    return min_gap


def down():
    min_gap = get_min_gap()
    for x in cluster:
        while cluster[x]:
            y = -heapq.heappop(cluster[x])
            board[y][x] = '.'
            board[y + min_gap][x] = 'x'


sys.setrecursionlimit(10000)
r, c, board, n, stick_list, dy, dx = init()
for i in range(n):
    sy = r - stick_list[i]
    sx = 0 if i % 2 == 0 else c-1
    step = 1 if i % 2 == 0 else -1
    mineral = get_mineral((sy, sx), step)
    if not mineral:
        continue
    my, mx = mineral
    board[my][mx] = '.'
    for d in range(4):
        ny = my + dy[d]
        nx = mx + dx[d]
        if 0 <= ny < r and 0 <= nx < c:
            if board[ny][nx] == 'x':
                cluster = dict()
                floating = True
                visited = [[False] * c for _ in range(r)]
                dfs((ny, nx))
                if floating:
                    down()
for i in range(r):
    sys.stdout.write(''.join(board[i])+'\n')