코딩테스트/백준
[BJ] 9663. N-Queen
jhk828
2021. 3. 2. 01:48
[BJ] 9663. N-Queen
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
백트래킹 문제!!!
1. 퀸들은 같은 행, 같은 열, 같은 대각선에 올 수 없다.
이때 같은 대각선에 올 수 없다는 말을, 바로 위의 행과 대각선 위치가 아니면 된다고 생각해서 푸는데 오래 걸렸다.
하나의 행 / 하나의 열 / 하나의 대각선에는 하나의 퀸만 올 수 있다고 생각하고 풀어야 한다.
2. cols 배열 -> idx행, cols[idx] 열에 퀸이 놓여있다는 뜻이다.
import java.io.*;
import java.util.*;
// 210220
public class Main_BJ_9663_NQueen {
static int N;
static int[] col;
static int cnt=0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
col = new int[N+1]; // 1열부터
setQueen(1);
System.out.println(cnt);
} // main
static void setQueen(int r) {
if (r>N) {
++cnt;
return;
}
// 해당 행의 1열부터 놓는다.
// 1열부터 놓을 수 있는지 체크하고. 놓을 수 있다면 다음 행
for(int c=1; c<=N; c++) {
col[r] = c;
if (check(r, c)) {
setQueen(r+1); // 해당 열에 둘 수 있으면 다음 행 시도
}
}
}
// 해당 행 이전까지, 같은 위치나 대각선에 있었는지 확인한다.
static boolean check(int r, int c) {
for(int k=1; k<r; k++) {
if (col[r]==col[k] || Math.abs(col[r]-col[k])==(r-k)) {
return false;
}
}
return true;
}
}