자바로 만드는 백트래킹 (Backtracking) + n queens 문제

백트래킹 알고리즘이란 모든 경우의 수를 검색하는 알고리즘 입니다.

"특정조건"을 만족하는 모든 경우의 수를 찾고 싶을 때 사용하면 유용해요.

백트래킹을 활용해서 풀 수 있는 대표적인 알고리즘 문제로 N Queens 문제가 있습니다.

N-Queens Problem

문제를 간단하게 설명하자면 

N*N 체스판에 N개의 Queen들이 "서로 공격 받지 않게" 놓는 위치를 구하는 것 입니다!

공격받지 않는 위치에 놓는 다는게 무슨 말일까요?

퀸 하나를 놓았을 때입니다.

퀸은 자신의 상하좌우를 공격할 수 있고, 대각선 방향도 공격할 수 있습니다.

만약에 퀸을 하나 더 놓아서 서로 공격 받지 않게 놓으려면 어떻게 해야 할까요?

   

그림처럼 체크한 곳중 한 곳에 퀸을 놓으면 서로 공격받지 않게 되겠죠?

이제 문제의 의도는 알았으니 문제로 다시 돌아가 볼까요.

N*N 체스판에 N개의 Queen들이 "서로 공격 받지 않게" 놓는 위치를 구하려면 

어떻게 해야 할까요...흠흠흠

위 그림은 N=4 일 때 답 중 하나입니다.

어떤 퀸도 서로를 위협하지 않죠.

고민을 해보시고 어려우신 분들은 아래로~ 꼬우!

S o l u t i o n 

...

이 문제를 자세히 들여다 보면 하나의 줄에는 하나의 퀸만 존재한다는 것을 알 수 있습니다.

!!!

그럼 "첫번째 줄"에 퀸을 놓고,

그 "다음 줄"에 조건에 만족하게 퀸을 놓고

....

이런식으로 "N번째 줄"에서도 문제없이 퀸을 놓을 수 있다면 답을 구할수 있겠네요.

먼저 N_queens 클래스를 만들어 보겠습니다.

class N_Queens{
	private int N;		//N*N할때의 N;
	private int cols[]; //i행에 들어갈 퀸의 좌표.
	
	public N_Queens(int N){
		this.N=N;
		cols = new int[N];
	}
	
}

주의깊게 봐야할 것은 cols 변수입니다.

N*N 체스판이라 이차원 배열이 필요할 것 같지만 

i번째 줄에 있는 퀸의 좌표만 알면 되므로  일차원 배열이면 표현이 가능합니다.

위와 같은 좌표라면 cols 에는 {2,0,3,1} 의 값이 들어간다고 생각하면 됩니다.

그럼 문제를 해결할 핵심 함수 back_tracking(int level)를 만들어 볼까요.

여기서 level은 현재의 위치(열) 을 뜻합니다.

 

무슨말인지 감이 안오시면 함수를 한번 보시겠습니다.

public void back_tracking(int level){
		//back_tracking 함수
		//level: 현재의 따질 행의 위치
		
		if(level == N){
			//현재 따질 위치가 N열인가? 
			//N-1까지 행이 있는데 N열까지 왔다는건
			//N-1까지 모두 조건을 만족한다는 얘기이므로 답을 출력.
			for(int i=0;i<N;i++){
				System.out.print(cols[i]);
			}
			System.out.println("");
		}
		else{
			//현재 상황 level-1까지는 모두 조건대로 되어있고
			//level열에 퀸을 놓는 상황.
		
			for(int i=0;i<N;i++){//퀸을 0번부터 N-1번까지 놓는 경우를 전부 따져본다.
				
				cols[level]=i; //퀸을 i에 놓는다.
				if(isPossible(level)){//퀸을 i에 놓은것이 가능한가?
					back_tracking(level+1); //그렇다면 퀸을 그 자리에 넣고 다음 행으로 진입
					
				}
			}
		}
		
	}

자세한 설명은 주석으로 써 놓았습니다.

back_tracking 함수를 요약하자면 back_tracking(3) 라고하면

level 0,1,2은 모두 조건을 만족하게 퀸을 놓았고, 

현재는 4번째 열에 머물러 있다라는 말이 됩니다. (level은 0부터 시작하므로...)

4번째 열에 퀸을 i에 놓고나서 if(isPossible(level))로 

4번째 놓은 퀸의 위치가 0,1,2줄에 있는 퀸들과 문제가 생기는지를 확인하고 

안생기면 다음 레벨(로 진입 하는겁니다.

그렇게 되면 4번째 줄까지는 퀸들은 모두 문제없이 잘 놓여져 있고

5번째 줄에서 또 코드를 실행하게 됩니다.

이런식으로 진행하다가 level이 N이 된다는건..

행은 N-1개가 있는데 N에 도달했다는건 N-1까지 퀸들이 잘 놓여졌다는 걸 뜻하므로

그 부분에서 함수를 종료해주면 됩니다.

(ㅠㅠㅠ 처음에는 이해가 잘 안가실 수 있는데 천천히 따라가 보면 이해하실수 있을 겁니다.!! 저도 처음에 너무 힘들었다는...)

이제 isPossible 부분만 설명이 되면 되겠네요.

isPossible 함수의 모습은 이렇습니다.

	public boolean isPossible(int level){
		for(int i=0;i<level;i++){
			//level 위치에 현재 시험할 퀸이 놓여져 있는 상태이고
			//우리는 그 퀸과 i= 0 ~ level-1 에 놓여있는 퀸이 문제를 일으키는지만 보면 된다.
			
			if(cols[i]==cols[level] || Math.abs(level-i)== Math.abs(cols[level]-cols[i])){
				//i번째 퀸의 위치와 level위치의 퀸이 같은 일직선상에 있는경우
				//또는
				//i번째 퀸의 위치와 level위치의 퀸이 대각선상에 있는 경우. 
				//밑변과 높이가 같으면 대각선상에 있다고 볼수 있다.
				return false;
				//이 경우는 불가능 하므로 false를 리턴
			}
		}
		return true;
		//위의 경우를 제외하면 가능하므로 true 리턴
	}

자세한 설명은 주석으로 써 놓았습니다.

isPossible(int level) 함수를 요약하자면

level 번째 놓여있는 퀸이 그 이전 퀸들에게 위협 받는 지를 조사하는 코드입니다.

"직선상에 놓여져 있거나" , "대각선 상에 놓여져 있는 경우" 가 아니면 

가능하다고 판단하고 true를 리턴합니다...

드디어 구현이 끝났습니다.

결과를 봐 볼까요?... 잘 나와야 할텐데요...

ㅠㅠㅠㅜ!! 잘 나옵니다.

아까 위에서 구했던 2031외에도 1302도 있다는 것을 알 수 있네요.

N=5일때

이렇게 많네요...

부족한 설명인데도 끝까지 봐주신 분들 감사합니다^^