minusie357   4년 전

스도쿠 푸는 방식을 기존의 전수 탐색 + 백트래킹이 아닌, 사람이 스도쿠를 풀듯이 가장 유추하기 쉬운 지점부터 탐색 + 백트래킹 방식으로 풀고 있습니다. 

도저히 시간 초과에 감이 집히는 부분이 없어서, 여러 다른 부분의 소스에서 최적화된 점을 참고하여 일부 수정하기도 했습니다. 

다른 질문에서 시간 초과가 난 최악의 예제 스도쿠들을 대상으로 했을 때는 훨씬 빠른 시간에 답을 도출하기도 하는데, 무엇이 문제일까요? 

부탁드립니다 ㅠㅠ.

djm03178   4년 전

이 문제 자체가 의도한 풀이가 일반적인 백트래킹에 맞추어져 있기 때문에, 그 외의 전략이 평균적으로는 더 좋다고 할지라도 데이터가 그런 전략이 잘 통하게 만들어져 있다고 장담할 수는 없습니다.

오히려 유추하기 쉬운 지점부터 시작하는 것이 실제로는 나중에 더 넘어가기 힘든 시점을 만든다거나, 복잡한 전략을 사용하는 오버헤드가 더 크게 작용할 수도 있는 등 의도된 풀이 외에는 어떤 것도 보장을 못한다고 봐야 합니다.

minusie357   4년 전

답변해 주셔서 감사합니다. 확실히 제가 푼 방식이 일부에서 빠르다고 전체에 일반화해서는 안되겠네요ㅠㅠ. 또한, 풀이 방식 이외에도 여러 가지 알려주셔서 도움이 되었습니다. 좋은 하루 되시길 바랍니다!

댓글을 작성하려면 로그인해야 합니다.