[백준] N-Queen

🔗 문제 보기 - [백준] N-Queen

📖 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

✍ 입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

📄 출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    static int[] board;  
    static int count;  
    static int n;  
  
    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];  
        nQueen(0);  
        System.out.println(count);  
    }  
  
    public static void nQueen(int col) {  
        if (col == n) {  
            count++;  
            return;  
        }  
  
        for (int i = 0; i < n; i++) {  
            board[col] = i;  
            if (check(col)) {  
                nQueen(col + 1);  
            }  
        }  
    }  
  
	// 백트래킹 메소드
    public static boolean check(int row) {
        for (int i = 0; i < row; i++) {  
            if (board[i] == board[row]) {   // 같은 행일 때 false
	            return false;
            }  
  
            if (Math.abs(row - i) == Math.abs(board[row] - board[i])) {   // 대각선일 때 false
	            return false;
            }  
        }  
  
        return true;  
    }  
}