Recursion의 응용 : n queen problem

- 입력으로 n을 받는다.

- n*n 2차월 배열을 생성

- n개의 퀸을 놓을때 어떠한 행,열,대각에 겹치는 퀸이 없게 놓는 방법.

- 퀸은 대각,행,열 한방향으로 끝까지 이동 가능

 

Backtracking

내가 결정을 하며 내려가다가 안된다는 것이 분명해 지면 내가 최근에 내린 결정을 번복하고

다른 결정을 내리는 알고리즘

상태 공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

 

상태 공간 트리

 

https://www.youtube.com/watch?v=xKGbWC-DPT4&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=6

 

상태공간트리란 ? 찾는 해를 포함하는 트리

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함

따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음.

 

상태공간 트리의 모든 노드를 탐색해야 하는 것은 아니다.

 

---

Design Recursion

 

return type queens(arguments)
{
    if non-promising
    	report failure and return;
    else if sucess
    	report answer and return;
    else
    	visit children recursively;
}

 

내가 어떤 노드에 도착하면 제일먼저 생각해야할 것은

 

이미 더이상 갈 필요가 없는 노드인가 아닌가를 생각해야한다.

아니라면 되돌아가면 그만이다.

 

두번째로 지금 도착한 노드가 내가 찾고있던 그 노드인가를 확인한다.

 

그렇지 않다면 

이 노드의 자식노드들을 방문해보는것이다.

 

int[] cols = new int [N+1];
boolean queens(int level)
{
    if non-promising
    	report failure and return;
    else if sucess
    	report answer and return;
    else
    	visit children recursively;
}

어떤 매개변수를 넘겨줄 것인가?

내가 현재 어떤 노드인지 알아야 하기때문에 깊이 정보를 넘겨준다.

 

2차원 배열을 사용할 필요가 없다.

 

cols[1] : 1번 말이 놓인 열 번호

cols[2] : 2번 말이 놓인 열 번호

cols[level] : level번째 말이 놓인 열 번호

 

int[] cols = new int [N+1];
boolean queens(int level)
{
    if(!promising(level))
        return false;
    else if (level == N)
    	return true;
    for(int i = 1; i<=N; i++){
    	cols[level+1] = i;
        if(queens(level+1))
        	return true;
       }
       return false;
}

level + 1 값을 재호출한다.