[SWEA] 2382. 미생물 격리

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

 2020년 1월 2일 2시 30분부터 2문제 풀기에 도전했고 성공했습니다. 이 문제를 1시간 8분에 풀기에 성공했고 다음 문제를 1시간 25분에 풀었습니다. 둘다 한번에 맞아서 아주 좋습니다. 두번째 문제가 구현하는데 살짝 오래 걸리긴 했지만 나름 만족스럽습니다. 

 

 미생물 군집의 위치와 미생물 군집의 수 그리고 이동방향이 주어집니다. 약품에 닿으면 움직이는 방향이 반대로 바뀌고 미생물의 수가 절반으로 줍니다. 그리고 한곳에서 2개이상의 군집이 모이게 되면 모이기 전 가장 큰 군집이 움직이던 방향으로 움직이게 됩니다. 문제의 내용자체는 어렵지 않았으나 구현하는데 조금 고민되는 점이 있었습니다.

 

 이문제의 포인트는 2개이상의 군집이 한 곳에 모일때인 것 같습니다. 이 부분이 까다로웠는데 저는 visited배열과 우선순위 큐를 이용하여 해결했습니다. 저의 문제 풀이 방식은 이렇습니다. 먼저 한시간이 지날때 마다 현재 군집이 있는 위치를 모두 찾아서 큐에 넣어줬습니다. 이 큐는 우선순위 큐라서 군집의 크기가 큰 순서대로 빠져 나오게 됩니다. 따라서 군집의 크기가 큰 순서대로 움직이게 됩니다. 이런 방식의 장점은 여러 군집이 합쳐질 때 방향을 결정하기에 좋습니다.

 

 만약 현재 군집이 이동하고자 하는 위치에 누구도 움직이지 않았다면(visited가 false) 그 장소에 방문했다고 visited배열에 표시해주고 그 위치에 이동시키고 마찬가지로 이동 방향도 기록해둡니다. 하지만 누군가 방문한 장소(visited가 true)로 옮기게 되면 자신보다 큰 군집이 그자리에 먼저 있었던 것이므로 자신의 개체수만 합쳐주고 방향은 바꾸지 않습니다.

이런 방식을 m시간동안 반복하여 풀어주었습니다.