[백준] 2933번 : 미네랄 - java

 

 

 

전체적인 단계 구상은 다음과 같다.

1. 주어진 높이와 방향에서 (왼->오 or 오->왼) 미네랄 파괴

2. 파괴 후, 공중에 떠 있는 클러스트가 있는지 확인 (BFS 탐색으로 클러스트에서 가장 아래에 있는 미네랄이 바닥이 아니라면, 떠 있는 것으로 간주)

3. 공중에 떠 있는 클러스트라면, 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지도록 이동시키기

 // 단,  떨어지는 동안 클러스터의 모양은 변하지 않는다. => 클러스트에 포함된 미네랄은 모두 같은 높이로 떨어진다.

 // 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우는 없다. => 공중에 떠 있는 1개의 클러스터를 발견하면, 더 이상의 클러스트 탐색은 할 필요가 없다.

 

 

1) x -> . 로 변경

 

 

2) 공중에 떠 있는 클러스트 확인

(1) 인접해있는 미네랄을 하나의 클러스트 번호로 set한다. 클러스트에 포함되지 않는 미네랄을 발견한다면 해당 미네랄 좌표에서 시작하여 연결된 하나의 클러스트를 찾는다.

(2) BFS 로 연결되어있는 모든 미네랄에 대해 클러스트 번호를 부여한다. 또한 클러스트를 떨어뜨리기 위해 포함된 미네랄 좌표를 모두 저장하고, 가장 아래에 위치한 좌표의 높이를 갱신한다.

=> 만약 클러스트의 가장 아래좌표가 바닥이 아니라면, 해당 클러스트는 공중에 떠 있는 것과 같다. 따라서 해당 클러스트를 떨어뜨리는 함수를 호출한다.

 

 

 

3) 클러스트 떨어뜨리기

(1) 기존에 위치한 미네랄들을 . 로 리셋한다.

(2) 떨어뜨리는 높이를 1에서부터 시작하여, 모든 미네랄좌표를 탐색하며, 하나의 미네랄이라도 바닥에 닿거나 다른 미네랄과 닿을 때까지 높이를 증가시킨다.

(3) dropHeight 를 구한 후, 기존의 미네랄좌표에 해당 높이만큼을 떨어뜨린 좌표에 미네랄을 다시 세팅한다.