[알고리즘 문제 풀이][파이썬] 백준 2933번: 미네랄

백준 1600 문제 링크: https://www.acmicpc.net/problem/2933

📑 문제 설명

• 동굴의 미네랄을 파괴함
• 이 때, 주어진 높이에서 파괴하는 순서는 왼쪽(창영), 오른쪽(상근)
• 미네랄을 만나서 파괴하면 그 즉시 파괴는 중단됨
• 파괴된 후, 미네랄의 클러스터가 발생함
• 클러스터는 중력의 힘에 의해 바닥 or 또 다른 클러스터를 만날 때까지 떨어짐

입력: 동굴의 크기, 동굴의 그래프(빈 공간과 미네랄의 조합), 막대를 던지는 횟수, 막대를 던지는 높이

출력: 막대를 다 던진 후의 동굴의 그래프

💡 문제 해결 방법
0) 미네랄 파괴

• 미네랄을 파괴하는 순서는 왼 -> 오 이기 때문에 짝수일 경우 왼쪽부터, 홀수일 경우 오른쪽부터 파괴를 시작한다.
• 이 때는 단순히 한 행에서 한 칸씩 옆으로 이동하다가 미네랄을 만나면 break 하면 된다.

1) 클러스터 찾기

• bfs를 사용하여 공중에 떠 있는 클러스터를 찾는다.
• 바닥과 붙어있는 클러스터는 해당되지 않기 때문에 초기 q에 바닥에 붙어있는 모든 클러스터를 넣어준다.
• bfs 탐색을 마친 후에 미네랄이면서 방문되지 않은 칸을 찾는다.(단순 반복문으로)

2) 클러스터 이동

• 클러스터는 모양을 유지한 채 이동한다.(중요)
• 그래서 단순히 떨어지는 칸을 세는 것이 아니라 가장 적게 떨어질 수 밖에 없는 칸에 맞춰서 이동해야 한다.

💻 코드

import sys
from collections import deque

# 왼, 오 순서대로 미네랄을 파괴
    # 미네랄을 파괴하면 그 즉시 탐색 stop
# 파괴 후 클러스터 발생 시(공중에 떠있으면 안됨)
    # - 바닥과 만날 때까지 이동
    # - 또 다른 미네랄을 만날 때 까지 이동

r, c = map(int, sys.stdin.readline().split())
graph = []
for i in range(r):
    temp = sys.stdin.readline()
    temp_list = []
    for j in range(c):
        temp_list.append(temp[j])
    graph.append(temp_list)
cnt = int(sys.stdin.readline()) # 막대 던지는 횟수
hlist = [] # 던지는 위치
hlist = list(map(int, sys.stdin.readline().split()))


def destroy_mi(y, turn): # 미네랄 파괴
    if turn % 2 == 1: # 오른쪽부터
        for i in range(c-1, -1, -1):
            if graph[y][i] == 'x':
                graph[y][i] = '.'
                break
    else: # 왼쪽부터
        for i in range(c):
            if graph[y][i] == 'x':
                graph[y][i] = '.'
                break
    return graph


def find_cluster(graph):
    visit = [[False for x in range(c)] for x in range(r)]
    q = deque()
    for i in range(c):
        if graph[r-1][i] == 'x':
            q.append((r-1, i))
    while q:
        x, y = q.popleft()
        adjlist = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
        for nx, ny in adjlist:
            if nx >= 0 and nx < r and ny >= 0 and ny < c:
                if visit[nx][ny] == False:
                    if graph[nx][ny] == 'x':
                        visit[nx][ny] = True
                        q.append((nx, ny))

    cluster = []
    for i in range(r-1, -1, -1):
        for j in range(c):
            if graph[i][j] == 'x' and visit[i][j] == False:
                # 클러스터 발생
                temp = [i, j]
                cluster.append(temp)
    if len(cluster) > 0:
        return cluster, 1, visit  # cluster 있음
    else:
        return cluster, 0, visit  # cluster 없음

def move_cluster(graph, cluster, visit):
    down_min = 1e9
    for x, y in cluster:
        down_cnt = 0
        for i in range(x+1, r):
            if graph[i][y] == '.':
                down_cnt += 1
            if graph[i][y] == 'x' and visit[i][y] == True:
                break
        down_min = min(down_min, down_cnt)
    for x, y in cluster:
        graph[x][y] = '.'
        graph[x+down_min][y] = 'x'
    return graph

for i in range(cnt): # 막대를 던지는 횟수만큼 반복
    # 1) 미네랄 파괴
    graph = destroy_mi(r - hlist[i], i) # 바닥부터 1
    # 2) 클러스터 조사
    cluster, check, visit = find_cluster(graph)
    # 3) 클러스터 이동
    if check == 1:
        graph = move_cluster(graph, cluster, visit)


for i in range(r):
    for j in range(c):
        print(graph[i][j], end = '')
    print()

💟 추가적으로 알게 된 점

• 코드 자체는 어렵지 않았지만 신경써야 할 부분이 많은 코드였다.
• 코테를 많이 준비하면서 이런 예외처리에 익숙해져야겠다.