백준 2933. 미네랄

tose33 2022. 8. 15. 15:40

2933번: 미네랄

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄

www.acmicpc.net

쉽지 않은 문제였다.

이 문제는 처음에 봤을때는 그냥 뿌요뿌요 처럼 한 부분의 미네랄이 사라지면 아래로 내릴수 있는 미네랄들을 내려서 쉽게 구현할수 있을것 같다. 하지만 문제는 미네랄들이 하나의 클러스터로 합쳐져 있는게 문제다.

하나의 미네랄을 보면 아래가 비어있어서 중력의 영향을 받을것 같아도, 해당 미네랄이 속한 클러스터 전체로 보면 중력의 영향을 받지 않을수 있기 때문에 그냥 미네랄의 아랫부분이 비었다고 내려버릴수가 없는 것이다.

1. bfs 알고리즘으로 클러스터들을 나눈다. 각 클러스터에 번호를 부여한다.

2. 클러스터들 중 떨어져야할 클러스터를 찾아서, 떨어져야할 클러스터들을 한칸 아래로 내린다.

bfs 탐색으로 클러스터에 속한 미네랄 중 하나라도 바닥에 있거나, 아래에 다른 클러스터의 미네랄이 있으면 떨어질수 없는 클러스터다.

떨어지는 클러스터가 없을때까지 2번을 반복한다.

2번의 핵심은 떨어질수 있는 클러스터들을 한 칸씩 내리는것을 반복하는 것이다.