[백준] 2933번 : 미네랄

2933번: 미네랄

2933번: 미네랄

🤔 문제분석

미네랄이 떨어지는것을 구현하는게 이 문제의 핵심 입니다. 미네랄이 떨어지는 후보를 만들고, 그 후보가 땅에 떨어질때까지의 최소 거리를 구한뒤 그 최소거리로 미네랄 클러스터들을 이동시킨다.

최소거리를 구하는 방법은 너비우선탐색으로 구하였는데, 모든 후보들을 큐에 넣고 땅에 닫거나 다른 클러스터에 접촉되는경우 너비우선탐색을 종료하고 최소거리를 구한다. 해당 최소거리로 떨어지는 후보들을 움직이면 된다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split())
table = [list(str(input().strip())) for _ in range(R)]
N = int(input())
attack_list = list(map(int, input().split()))

LEFT = 0
RIGHT = 1

def change_direction(direction):
    if direction == LEFT:
        return RIGHT
    else:
        return LEFT

def attack(h, direction):
    if direction == LEFT:
        for i in range(C):
            if table[h][i] == 'x':
                table[h][i] = '.'
                return
    else:
        for i in range(C-1, -1 ,-1):
            if table[h][i] == 'x':
                table[h][i] = '.'
                return

def is_land(y, x):
    return y == R-1

def is_range(y, x):
    return R > y >=0 and C > x >=0

def find_min_height(queue):
    min_height = R
    for y, x in queue:
        cnt = 1
        for i in range(y+2, R):
            if (i, x) not in queue:
                if table[i][x] == 'x':
                    min_height = min(min_height, cnt)
                    break
            cnt += 1
            
        min_height = min(min_height, cnt)
    return min_height

def move(group):
    queue = deque()
    for q in group:
        queue.append((q[0], q[1], 0))
        table[q[0]][q[1]] = '.'
        
    while queue:
        y, x, cost = queue.popleft()
        
        if y == R-1 or table[y+1][x] == 'x':
            for n_y, n_x in group:
                table[n_y + cost][n_x] = 'x'
            break
                
        queue.append((y+1, x, cost + 1))

def move_down():
    # 바닥까지 혹은 크리스탈까지의 최소 거리를 찾아서 내린다.
    visited = [[False for _ in range(C)] for _ in range(R)]
    groups = []
    for i in range(R):
        for j in range(C):
            if table[i][j] == 'x' and not visited[i][j]:
                land_flag = False
                queue = deque()
                queue.append((i, j))
                group = []
                group.append((i, j))
                visited[i][j] = True
                
                while queue:
                    y, x = queue.popleft()
                    if is_land(y, x):
                        land_flag = True
                    
                    for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        ny, nx = dy + y, dx + x
                        if is_range(ny, nx) and not visited[ny][nx] and table[ny][nx] == 'x':
                            visited[ny][nx] = True
                            queue.append((ny, nx))
                            group.append((ny, nx))
                            
                if not land_flag:
                    groups.append(group)
                    
    for group in groups:
        move(group)
                    

direction = LEFT
for i in range(N):
    attack(R - attack_list[i], direction)
    # print("after attack", (attack_list[i], direction))
    # for t in table:
    #     print(''.join(t))
    
    
    move_down()
    
    # print("after move")
    # for t in table:
    #     print(''.join(t))
    
    direction = change_direction(direction)

for t in table:
    print(''.join(t))

🎯 피드백 및 개선사항

클러스터들을 얼마나 움직여야 하는지 생각해 보는것이 이 문제의 포인트 이었던것 같습니다. 처음에는 모든 후보들을 아래로 내려보면서 다 시도해보았지만 너비우선탐색으로 최소거리를 더 빠르게 알아 낼 수 있습니다. 복잡한 구현문제는 짧은 기능으로 쪼개고, 복잡한 로직은 천천히 더 많이 생각해 보는 시간을 갖도록 해야겠습니다 😀