[BOJ] 2933번 미네랄

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

막대를 던질때마다 필요한 로직으로 다음 5단계 TODO를 적고 하나씩 코드를 작성해 나갔다.
1. 미네랄 제거
2. 클러스터마다 묶어서 좌표 저장(BFS나 DFS)
3. 클러스터 중에 떨어질 클러스터있나 찾기
4. 떨어질 클러스터에서 이동해야 할 좌표수 구하기
5. 이동하기

이때, 5번째 단계에서 이동할때 맨 아래에 있는 미네랄부터 이동시켜야 문제가 되지 않는다. 이를 위해 정렬이 필요하다.

또, 문제에서 클러스터가 떨어질 때, 그 클러스터 "각" 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다고 되어있는데,

처음에 그냥 클러스터의 가장 아래 부분만 닿는다고 생각하고 접근하여 삽질을 하다가 반례를 보고 깨달았다. "각"을 제대로 보자.

import sys
sys.setrecursionlimit(10**6) # recursion limit
from collections import defaultdict

def mineral_destroy(direction, height_idx):
    if direction == "left":  # 왼쪽에서 공격
        range_with_direction = range(C)
    else:
        range_with_direction = reversed(range(C))

    for i in range_with_direction:
        if minerals[height_idx][i] == "x":
            minerals[height_idx][i] = "."
            return


def bfs(minerals, i, j, is_visited, coordinates):
    coordinates.append((i, j))
    is_visited[i][j] = True

    for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        new_i = i + dx
        new_j = j + dy
        if 0 <= new_i <= R - 1 and 0 <= new_j <= C - 1:
            if minerals[new_i][new_j] == "x" and not is_visited[new_i][new_j]:
                bfs(minerals, new_i, new_j, is_visited, coordinates)


def find_cluser(minerals):
    clusters = []
    is_visited = [[False] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if minerals[i][j] == "x" and not is_visited[i][j]:  # 새 클러스터
                coordinates = []
                bfs(minerals, i, j, is_visited, coordinates)
                clusters.append(coordinates)
    return clusters


def find_move_dx(minerals, bottom_coordinates):
    # 열마다 가장 아래 좌표들
    max_height_dict = defaultdict(int)
    for x, y in cluster:
      if x > max_height_dict[y]:
        max_height_dict[y] = x
    bottom_coordinates = [(x,y) for y,x in max_height_dict.items()]
  
    min_dx = sys.maxsize
    for x, y in bottom_coordinates:
        cnt = 0
        x += 1  # 한칸건너서부터 카운팅
        while x <= R - 1 and minerals[x][y] != 'x':
            x += 1
            cnt += 1
        min_dx = min(min_dx, cnt)
    return min_dx


R, C = map(int, input().split())
minerals = [list(input()) for _ in range(R)]
N = int(input())
heights = list(map(int, input().split()))

for i, height in enumerate(heights):
    height_idx = R - height

    # 1 미네랄 제거
    direction = "left" if i % 2 == 0 else "right"
    mineral_destroy(direction, height_idx)

    # 2 클러스터마다 묶어서 좌표 저장하기 [[(2,4), ...], [], []]
    clusters = find_cluser(minerals)

    # 3 클러스터 중에 떨어질 클러스터있나 찾기
    for cluster in clusters:
        max_height_idx = max(x[0] for x in cluster)
        if max_height_idx != R - 1:  # 중력으로 떨어져야할 클러스터
            # 4 이동해야할 x좌표 구하기
            move_dx = find_move_dx(minerals, cluster)

            # 5 이동(!!아래에 있는 것부터 옮겨야됨)
            cluster.sort(key = lambda x: -x[0])
            for x, y in cluster:
                minerals[x][y] = '.'
                minerals[x + move_dx][y] = 'x'

# 정답 프린트
for i in range(R):
    print(''.join(minerals[i]))