백트랙킹- N-QUEEN(백준 9663번)

1. 백트래킹을 이용한 N-QUEEN 문제 (백준 9663번)

---

---

2.백트랙킹을 이용한 풀이

---

package recursiveandbacktracking;
import java.util.Scanner;
 
public class Baekjun9663BacktrackingNQueen {
    static int[] iArr;
    static int count;
    static int N;
    
    //퀸이 놓일수 있는가?
    static boolean promising(int[] iArr,int N,int row) {
        for(int i=0;i<row;i++) {
            if(iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i])) {
                return false;
            }
        }
        return true;
    }
    static void nQueen(int[] iArr,int N,int row) {
         for(int i=0;i<N;i++) {
             iArr[row]=i;
             //퀸이 놓일수 있다면? 다음 행에 대해 퀸을 놓는다. 혹은 마지막 행이면 count수를 증가시켜준다.
             if(promising(iArr, N, row)) {
                 if(row==N-1) count++;
                 else {
                     nQueen(iArr, N, row+1);
                 }
             }
         }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        iArr=new int[N];
        nQueen(iArr, N, 0);
        System.out.println(count);
    }
}
 

4X4 체스판에서의 예를 들어보면 처음에 nQueen(iArr,4,0) 이라는 함수를 호출한다. 이 함수의 뜻은 1번째 행에 퀸을 놓는다 라는 뜻이다. 함수 속에 들어가게 되면 1번째 행에는 퀸을 1,2,3,4 열에 퀸을 놓을 수 있다. 이것을 각각의 경우로 따지기 위해 for문의 인덱스를 0<=i<N 이라는 값으로 셋팅 해준것이다. 그리고 iArr[0]=0 이 들어가게 된다. 이 뜻은 1번째 행의 1번째 열에 퀸을 놓겠다 라는 뜻이다. 그런다음 조건문안에 promising(iArr,4,0) 이라는 함수를 호출하게 된다. 이 함수 안에 들어가게 되면 지금 행의 이전까지의 퀸을 놓은 경우에 따라 지금 놓은 퀸의 위치가 유효한가를 따져보는 함수이다. 하지만 row가 0이므로 이전의 놓은 값은 아무것도 없기에(i<0) for문 자체를 돌지 않으므로 return 값은 true가 되어 퀸을 놓을 수 있게 된다. 여기서 promising 함수안의 조건문을 보면 iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i]) 이라는 조건이 있다.

이 조건은 퀸의 성질을 나타낸 것인데 퀸은 자신이 놓인 곳에서 행,열, 대각선 아무 곳이나 이동하여 공격 할수 있다라는 성질을 이용해 만약 이전에 놓였던

퀸들의 위치에서 행,열,대각선 위치와 지금 놓은 퀸의 위치가 같다면 false를 리턴하라는 조건문이다. 이렇게 row를 하나씩 증가시켜가며 퀸을 놓는 것이다.

만약 promising이 false라면 다음 퀸을 놓지 않고 for문으로 다시 돌아가 i를 1 증가시켜 다음 위치에 퀸을 놓았을때를 비교 한다.(백트랙킹) 만약 해당 열에

어느곳에도 놓을수 없다면 이전 퀸으로 돌아가 이전 퀸의 위치를 i+1로 변경해서 다시 퀸을 놓는 경우의 수를 따져보는 것이다.(백트랙킹)

입력:

8

출력:

92