N Queen문제

공부한 사이트

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

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

 

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

 

 

문제: 체스 판에 상하좌우, 대각선에 하나 이상의 말이 놓이지 않도록 할 수 있는가?

 

해결방법

<Back Trackinh 기법>

   모든 경우의 수를 *상태공간트리로 나타낼 수 있을 때

   노드 하나하나를 탐색하며 해의 조건에 부합하지 않을 경우 최근에 내렸던 결정을 번복하고 다른 선택을 하면서

   정답을 찾아가는 알고리즘이다.

 

   (종류로는  깊이 우선탐색(DFS), 너비우선탐색(BFS), 최선우선탐색이 있다.)

    여기에서 DFS를 이용함.

    상태공간트리의 최상위 노드에서 한 방향으로 바닥에 도달할때 까지 내려가는 방식.

    내려가다가 해가 되기 위한 조건을 위반할 경우 다른 가능성을 탐색하기 위해 노드를 올라간다.

 

     재귀로 구현 가능

* 상태공간트리: 모든 경우의 수를 트리의 형태로 나타내는 것. 찾는 해가 존재한다면 반드시 어떤 한 노드에 해당함.

   

- queens()는 매개변수로 현재 위치를 받아 그 이전 말들과 충돌이 일어나지는 않는지 확인하고, 

  일어나지 않으면  다음 행에 말을 두는 재귀함수이다.

   반환형은 true: 충돌x , false: 충돌o

 

-  현재 위치를 2차원 배열로 하지 않은 이유: 현재 위치를 표현하기 위해 행, 열의 값이 필요, 일차원배열의 인덱스와 값으로 충분히 표현가능,  cols[] 전역변수를 이용해 위치값 일부를 전달한다.  (매개변수 복잡x)

 

- 매개변수 level의 의미는 이전 말들에 대해 충돌(infeasible)이 없었음을 의미함.

 

package Recursion;

public class N_Queen {
	private static int N=4;
	int[] cols = new int[N+1];
	
	/* 현재 위치를 매개변수로 전달 (N정사각형의 행)
	 * 이전 말들과 충돌하지 않는지 확인 후 t: level+1행에 말을 둔다, f: level행의 다른 위치에 말을 둔다.
	 * 
	 * 반환형: true: 충돌하지 않는다. false: 충돌한다.
	*/
	boolean queens(int level) {	
		
		if(!promising(level)) return false;	// 충돌하는지 확인
		else if(level == N) {	// 원하는 해가 나왔는지 확인 (말이 끝까지 다 놓였다는 의미로 true를 반환하고 종료한다.)
			for(int i=1; i<=N; i++) {	// 모든 말의 위치를 출력
				System.out.println("("+i+", "+cols[i]+")");
			}return true;	
		}else {	// 다음 행(cols[level+1])에 말을 둔다.
			for(int i=1; i<=N; i++) { // i= 열
				cols[level+1] = i; //다음 레벨에 말을 다 놓아본다.
				if(queens(level+1))
					/* 말을 둔 위치가 이전과 충돌하는지 확인하고 말을 두기 위해 recursion
					 true: cols[N]까지 충돌이 없다, false: 이전 말들과 충돌이 있어 끝까지 말을 놓지 못하는 경우,
					 */ 
					return true;
			}return false;
		}
		
		
	}
	// level단계의 말과 이전에놓인 다른 말들이 충돌하는지 확인하는 검사
	boolean promising( int level) {
		
		for(int i=1; i<level; i++) {
			if(cols[i]==cols[level]) return false; //같은 열에 높였는지 검사
			else if(level-i == Math.abs(cols[level]-cols[i]))//대각선에 놓였는지 검사
				return false;
		}return true;	//(for문 수행x)level 이전 행이 없을 경우, (for문 수행o)이전 행에서 충돌이 없는 경우
	}
	public static void main(String[] args) {
		N_Queen q=new N_Queen();
		q.queens(0); // 매개변수로 0 (queens()는 다음 말을 놓는 함수라서)
	}

}