백준 9663 N-Queen

가장 대표적인 백트래킹 문제로 알고리즘 수업을 들을 떄 풀어본적이있는 문제였다. 열과 증가대각선, 감소대각선을 각 배열로 만들어서 더 적은 실행시간으로도 문제를 풀 수 있다는 것을 배웠다. 

 

첫번째 방법 

package 백트래킹;
 
import java.io.*;
 
public class N_Queen {
    static int[][] board;
    static int n, cnt = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n + 1][n + 1];
        NQueen(1);
        System.out.println(cnt);
 
    }
 
    public static void NQueen(int num) {
        if (num == n+1) {//n행 까지 다놓은 상태라면 조건을 만족하는 경우
            cnt++;
            return;
        }
        for (int i = 1; i <= n; i++) { // 놓는 열 설정
            if (isvalid(num, i)) { // 놓을 수 있다면
                board[num][i] = 1; // 놓고
                NQueen(num + 1);   // 다음 행
                board[num][i] = 0;  // 호출되고나서 지우기
            }
        }
 
    }
    private static boolean isvalid(int num, int j) { //열을 매개변수로 입력받음
        int flag = 1;
        while (num - flag > 0) {
            if (board[num - flag][j] == 1) {
                return false;
            }
            flag++;
        }
        flag = 1;
        while (num - flag > 0 && j - flag > 0) {
            if (board[num - flag][j - flag] == 1) {
                return false;
            }
            flag++;
        }
        flag = 1;
        while (num - flag > 0 && j + flag <= n) {
            if (board[num - flag][j + flag] == 1) {
                return false;
            }
            flag++;
        }
        return true;
    }
 
 
}
 

package 백트래킹;
 
import java.util.Scanner;
 
public class N_Queen2 {
    static int n, ans;
    static int[] col, inc , dec;
 
    public static void main(String[] args) {
        col = new int[10]; //열
        inc = new int[20];//증가 대각선
        dec = new int[20];//감소 대각선
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        NQueen2(1);
        System.out.println(ans);
 
    }
    public static void NQueen2(int num){
        if(num>n){
            ans++;
            return;
        }
        for (int i = 1; i <=n ; i++) {
            if(col[i] == 0 && inc[num+i] == 0 && dec[n+(num-i)+1] == 0){ //dec의 경우 음수방지를 위해 n을 더한다
                col[i]=inc[num+i]=dec[n+(num-i)+1] = 1;
                NQueen2(num+1);
                col[i]=inc[num+i]=dec[n+(num-i)+1] = 0;
            }
 
        }
    }
}