백트렉킹
-
[Javascript] - N-Queens 구현하기Programming/Javascript 2019. 4. 12. 09:53
N-Queens란 무엇인가 - N * N의 크기의 체스판에 퀸을 N개 배치하는 문제이다 - N개의 퀸은 서로 공격할 수 없다 - 체스에서 퀸은 자신의 위치에서 상하좌우, 그리고 대각선 방향으로 공격을 할 수 있다 - 위의 문제를 구현하기 위해서는 백트렉킹 알고리즘을 사용해야한다 백트렉킹이란 무엇인가 - 특정 노드에서 유망성을 점검하고, 유망하지 않다면 그 노드의 부모 노드로 돌아가서 다른 노드에 대한 검색을 계속하는 절차 - 백트렉킹 알고리즘은 전수조사 방법중 하나인 깊이우선탐색으로 시작한다 그리고 각 노드에서 유망하지 않은 노드들은 탐색 하지 않고 유망한 노드에 대해서만 탐색을 진행한다 (가지치기, Pruning) - 탐색의 순서 1. 깊이 우선 탐색을 실행 2. 각 노드의 유망성 검사 3. 유망하다면..