1799번 - 비숍
n queen problem에서는 하나의 퀸이 행을 점유하기때문에 행을 건너뛰면서 백트래킹하여 비교적 빠르게 해결했는데
비숍은 대각선만 점유하기때매 다음 depth로 넘어가는 단계에서 대각선 체크 말고는 가지치기 방법이 떠오르지 않습니다
힌트좀 알고싶습니ㄷㅏ
체스판을 생각하면 검은칸에 있던 비숍은 검은칸 으로만 이동이 가능하고, 흰 칸에 있던 비숍은 흰칸만 이동이 가능합니다.
이 성질을 이용하면 시간안에 답은 나오는 것 같습니다.
그런데 시간복잡도 계산은 못하겠어요...
댓글을 작성하려면 로그인해야 합니다.
kyg516 8년 전
n queen problem에서는 하나의 퀸이 행을 점유하기때문에 행을 건너뛰면서 백트래킹하여 비교적 빠르게 해결했는데
비숍은 대각선만 점유하기때매 다음 depth로 넘어가는 단계에서 대각선 체크 말고는 가지치기 방법이 떠오르지 않습니다
힌트좀 알고싶습니ㄷㅏ