알고리즘: 재귀함수(5) 예제 N Queens

※ 두 가지 코드 형식을 학습해 업로드한 코드는 다름.

 

채스의 Queen을 생각하면 됨

    말은 어떠한 대각선과 행, 열에서 절대 겹치면 안 됨

 

상태 공간 트리

 

 

    찾는 해를 반드시 포함하고 있는 트리

    이 트리는 모든 가능한 경우의 수를 놓은 것이기 때문에 반드시 노드에 찾는 해가 존재한다는 것임

 

    즉, 해가 존재한다면 그것은 반드시 이 트리의 어떠한 노드에 해당한다는 것으로 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

    하지만 그렇다고 하여 모든 노드를 탐색해야 한다는 것은 아님.

    

    만약 해의 조건을 만족하지 않는다면 해당 노드는 infeasible 하다고 체크하며,

    가장 최근에 진행하였던 노드로 돌아가 다른 선택지의 노드를 체크함.

 

백트래킹 (Backtracking)

 

    수행하다가 수행 방법이 잘못되었음을 확인하면 가장 최근의 방법으로 돌아가 다른 선택을 수행하는 것을 번복하는 것

    상태 공간 트리를 깊이 우선 탐색으로 탐색해 해를 찾는 알고리즘을 이야기 함

 

    깊이 우선 탐색은 트리 탐색 기법의 대표적 기법 중 하나이며,

    주로 Recursion을 이용해 구현함

 

 

코드