알고리즘/알고스팟
N-Queen
devmoons
2014. 8. 7. 01:06
문제: NQUEEN / 조합탐색
해결전략 1. 이중배열 이용
[출처] [AOJ 문제] N-Queen|작성자 DevMoon
1) 퀸을 놓기전에 상, 좌상, 우상 방향에 퀸이 있는지 검사한다.
2) 있으면 다른 칸에 놓는 것을 시도하고, 없으면 그 자리에 놓는다.
3) 다음 퀸을 놓기위해 재귀함수를 호출한다.
[출처] [AOJ 문제] N-Queen|작성자 DevMoon
코드: https://github.com/xgate/algospot/blob/master/SEARCH/NQUEEN1.cpp
해결전략 2. bit 연산 이용
1) queen의 위치를 bit로 표현한다.
2) 위의 행에 있는 queen과 겹치는지 bit 연산을 이용해서 판단한다.
3) 다음 퀸을 놓기위해 재귀함수를 호출한다.
[출처] [AOJ 문제] N-Queen|작성자 DevMoon
코드: https://github.com/xgate/algospot/blob/master/SEARCH/NQUEEN2.cpp