HwangHub

🤔 Intuition BFS를 이용한 완탐으로 보였다. 귀신이 남우를 따라잡는 여부를 어떻게 알 수 있나 기준을 잡는 게 중요했는데, 귀신이 남우보다 먼저 목적지에 갈 수 있는 경우에는 무조건 귀신이 남우를 따라잡을 수 있는 것으로 봤다. 여기서 고민을 했던 부분은 최악의 경우 10^6 개의 귀신을 가질 텐데, 이들이 모두 BFS를 돌면 시간을 쉬이 초과할 것이다. 따라서 탐색을 할 귀신을 선정하는 게 중요한데, 나는 도착지와 맨해튼 거리가 가장 가까운 귀신만 검사해줬다. 어차피 가장 가까운 귀신의 이동 거리만 필요하기 때문이다. (솔직히 처음에 제출할 때에는, "에이 그래도 이게 뻑이 안나도록 문제를 줬을거야 누가봐도 BFS 문제인데?" 라는 아주아주 안일한 생각을 했다. 결론은, 문제에서 단순 완탐이..