[백준 2025] 나이트투어

티어: 루5

 

https://www.acmicpc.net/problem/2025

 

나이트투어의 정석이라고도 할 수 있는 문제이다. 256개의 테케중 224개 이상을 맞으면 ac를 받을 수 있다.

 

보드의 크기인 N의 제한이 666이하이기 때문에, 모든 경우를 다 체크해보는건 불가능하다. 이럴때 정확성을 살짝 포기하고 속도를 높이는 것이 바로 휴리스틱이다. 필자는 나이트투어 문제에서 가장 유명한 방법인 Warnsdorf's rule을 이용했다.

Warnsdorf's rule은 나이트가 다음에 갈 수 있는 칸들에 대해, 나이트가 그 위치로 움직였을 때 갈 수 있는 칸의 수가 가장 적은 칸으로 움직인다는 방법이다. 만약 그러한 칸이 2개 이상이라면, 무작위로 움직인다.

https://en.wikipedia.org/wiki/Knight%27s_tour

하지만 이것만으로는 부족하다. N의 제한이 충분히 큰 이 문제는 Warnsdorf's rule만으로 구현한다면 정확도는 50%에 미치지 못한다.

따라서 다른 조건을 찾아봐야하는데, 이때 사용할 수 있는것이 바로 Arnd Roth가 제안한 방법이다.

Arnd Roth는 Warnsdorf's rule에 더해서, 중앙에서 가장 멀리 떨어져있는 칸으로 움직이는 방법을 제안했다. 이 방법을 통하면 2000이하의 N에 대하여 99% 이상의 정확도를 자랑한다고 한다. 그리고, 적어도 이 문제에서는 사실이였다.

224개 라는 조건은 생각보다 매우 느슨하다.

 

//치터가 많아져 코드는 생략합니다.

 

원래는  Warnsdorf's rule을 기반으로 동점이 있다면 Arnd Roth 방법을 사용하기만 해도 ac를 받지만,
필자는 256개를 다 맞고싶다는 욕심이 들어 동점인 경우 모든 칸들에 대하여 Warnsdorf's rule을 한번 더 돌려줬다.
그럼에도 불구하고 256개를 다 맞진 못했다.

 

+2025/02/16

지금까지 정해로 여겨져왔던 휴리스틱(Warnsdorf's rule)을 뒤엎고 256/256 ac를 받는 새로운 방법이 발견되었다. 정말.. 세상은 넓고 천재는 많은 것 같다.