728x90
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
- 백트래킹
- 입력받은 n에 대해 n+1개의 배열 생성( col = new int[n+1] ) ----> 1번 인덱스부터 시작하게함
- col배열의 인덱스는 행의 번호를 의미하고 그 인덱스의 값은 그 행의 몇 번째 칸에 놓일 수 있는지를 의미한다. ( ex.. col[1] = 1 ----> 1번 행 1번 칸에 퀸을 둔다 )
- 메인함수(39번 라인)에서 첫 번째 행에 첫번째 칸에 퀸을 둔 뒤 queen함수 호출
- queen함수의 초기부분에서 row(행 번호)가 n 보다 큰지를 검사한다. 이 조건문은 n개의 행까지 퀸을 모두 놓았다는 것을 의미하므로 count를 1 증가시켜준다.
- 인자로 전달된 row에 대해 col[row]의 몇 번째 칸에 퀸이 놓일 수 있는지 isPossible함수를 통해 검사한다
- isPossible 함수에는 현재 행의 번호가 인자로 전달되며 이전 행에 놓인 퀸이 위치와 현재 행의 퀸의 위치를 비교하여 검사.
- isPossible 함수의 조건문 두개가 의미하는 바는 다음과 같다
28번라인) 이전에 놓인 퀸들의 위치와 현재 행의 위치의 퀸이 같은 열에 존재한다면 false를 반환
29번라인) 이전에 놓인 퀸들의 위치와 현재 행의 위치가 대각선 상에 존재한다면 false를 반환
- 만약 위의 두 조건에 모두 해당하지 않는다면 퀸이 놓일 수 있다는 것을 의미하기 때문에 queen함수의 18번라인으로 복귀하여 재귀함수를 호출하게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
package backjoon;
import java.util.Scanner;
public class Main {
static int col[];
static int count;
static int n;
static void queen(int row) {
if(row > n) {
count++;
}
for(int i=1; i<=n; i++) {
col[row] = i;
if(isPossible(row)) {
queen(row + 1);
} else {
col[row] = 0;
}
}
}
static boolean isPossible(int c) {
for(int i=1; i<c; i++) {
if(col[i] == col[c]) return false;
if( (Math.abs(col[i] - col[c])) == (Math.abs(i - c))) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=1; i<=n; i++) {
col = new int[16];
col[1] = i;
queen(2);
}
System.out.println(count);
}
}
|
cs |
728x90
반응형
'개발하자 > Baekjoon' 카테고리의 다른 글
| 백준 6603번 - 로또 (0) | 2020.01.15 |
|---|---|
| 백준 1987번 - 알파벳 (0) | 2020.01.15 |
댓글