kyg516   8년 전

n queen problem에서는 하나의 퀸이 행을 점유하기때문에 행을 건너뛰면서 백트래킹하여 비교적 빠르게 해결했는데


비숍은 대각선만 점유하기때매 다음 depth로 넘어가는 단계에서 대각선 체크 말고는 가지치기 방법이 떠오르지 않습니다


힌트좀 알고싶습니ㄷㅏ

mastojun   8년 전

체스판을 생각하면 검은칸에 있던 비숍은 검은칸 으로만 이동이 가능하고, 흰 칸에 있던 비숍은 흰칸만 이동이 가능합니다.

이 성질을 이용하면 시간안에 답은 나오는 것 같습니다.

mastojun   8년 전

그런데 시간복잡도 계산은 못하겠어요...

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