- boj 31399 ac, 플2
아리스가 청소하는 문제 Hard 버전이다.
태그를 까기 전까진 정말 헬게이트였다. 아무리 머리를 짜내도 신박한 아이디어가 없었다. 1시간 정도 고민하면서, 태그에 분명 애드 혹이 붙어있을거라고 생각했다. 그런데 태그에는 난데없이 유니온 파인드가 보이는게 아닌가.. 무릎을 탁 치고 바로 구현에 들어갔다.
이동 경로에서 반복이 되는 주요 부분은 당연하게도 먼지를 제거한 칸들이다. Easy에서 활용했듯이 같은 칸에서 같은 방향으로 움직이면, 먼지가 있는 칸을 만나기 전까지는 항상 같은 경로로 움직이게 된다. 이 두가지를 합쳐서 모든 좌표, 방향에 대해 정점으로 구성해 유니온 파인드를 써서 특정 좌표, 방향일 때 도달하게 되는 도착점을 부모로 정하면 반복되는 이동 없이 빠르게 먼지가 있는 칸들만 돌아다닐 수 있다. 사이클 판별은 Easy와 똑같이 먼지를 제거하지 않았는데 같은 칸 같은 방향이 나타난다면 중지하면 된다.
다시는 블루아카이브만 보고 깝치지 않겠다.
