Backtracking _N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

N-Queen(해당 코드는 밑에 첨부)

문제

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

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

 

N * N 판에 각 행 당 퀸이 있을경우 서로 공격할 수 없게 하는 경우의 수를 구하는 프로그램을 작성하는 것이다.

여기에 퀸의 주 업무는 해당 모든 방향으로 갈 수 있다.<오른쪽,왼쪽 직선(칸의 수 상관 x) 대각선 모두!>

입력

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

==> 체스판의 크기!

출력

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

==========================================================================

 

 

먼저 설명에 앞서

x축은?         -> 열

y축은?         -> 행

 

N과 M을 풀때와 마찬가지로 해당 경우의 수를 물어보는 것이다.

해당 경우의 수가 만족하려면?!

=> 각 행에 퀸이 위치하면 된다 즉 N개의 퀸이 x,y좌표에 모두 들어있으면 된다.

 

그리고 다음으로 순차적으로 첫번째 행(y축)에 1,2,3,4번쨰에 퀸이 있는 경우의 수

그리고 다음 행에 1,2,3,4번쨰에 퀸이 있는 경우의 수 

.....

쭊쭊쭊쭊

계속적으로 이전 퀸의 위치에 의해 다음 퀸의 위치가 정해지는 것을 보고 재귀를 사용할 수 있으며,  이전의 퀸이 정해지면 다음의 퀸이 정해지고 또 다음의 퀸이 정해지면 다다음의 퀸이 정해지고 .... 그리고 안되면 다시 전으로 돌아 다음 열에 계속적으로 이루어지므로 DFS를 생각할 수 있다.

 

경우의 수를 만족하지 못하는 대표적인 예)

 

계속적으로 생각을 하다보면 첫번째 행에 1열에 퀸이 있고 두번째 행에 3열에 있고 세번쨰 행에 1열 (x) 첫번째 열과 세번째 열에 퀸이 있으면 서로 공격할 수 있다.

 

※퀸이 서로 공격하지 못하기 위한 조건 (반복적으로 적용해야 한다.)

----------------가정 해당 체스판의 크기 N이 4일 경우

1) 같은 x축에 위치 하면 안됨.

2) 같은 대각선상에 위치하면 안됨

  2.1) 좌측 하단과 우측 상단일 때.  (1,4)  (2,3)  (3,2) .....     i,j 라고 할 때    i+j==N+1 인 조건

  2.2) 우측 하단과 좌측 상단일 때.  (1,1) , (2,2) (3,3) .....     i,j 라고 할 때    i-j==0 인 조건

 

 

소스코드에

N_Queen 은 DFS이다.

 

 

import java.util.Scanner;

// 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력
/*
* 각 행에 퀸을 하나씩 넣고 서로 공격하지 않는 경우의 수를 따져봐야 한다.
* 1) y좌표가 일치하는지
* 2) 좌측하단과 우축 대각선 x+y 같은값
* 3) 좌측상단과 우측 하단 x-y 같은 값.
* */
public class N_Queens {
static int N;
static int Number_Of_Case = 0;
static boolean chessPan[][];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
chessPan = new boolean[N + 1][N + 1]; // 0row
for (int i = 1; i <= N; i++) {
int[] x = new int[N + 1]; // N * N 행렬이기에 열도 인덱스를 N 까지 갖을 수 있게 한다.

// 1행 i열에 퀸을 놓았다.
x[1] = i; // 각 x축의 관한 좌표
N_Queen(x, 1);
}


System.out.println(Number_Of_Case);
}

public static void N_Queen(int[] x, int y) //DFS 유사하다.
// 해당 y의 값이 퀸의 갯수. , x[]는 각 행(y축)에 퀸이 위치한 열(x축의 좌표이다)
{
if (y == N) {
Number_Of_Case++;
} else {
// 1열 부터 N 열까지 반복하면서 (row+1, i)에 퀸을 놓을 수 있는경우가 있는지 확인한다.
// 있으면 다음행의 dfs를 호출한다.
for (int i = 1; i <= N; i++) {
x[y + 1] = i;
if (check(x, y + 1)) {
N_Queen(x, y + 1);
}
}
}
}

public static boolean check(int[] y, int x) {
// 1행부터 row 행까지 같은 열 혹은 대각선에 위치하는 퀸이 있는지 확인한다.
// y축으로 증가 시키면서 체크.
for (int i = 1; i < x; i++) {
// i 행과 row 행의 열 값이 같으면 퀸을 놓을수 없다.
if (y[i] == y[x])
return false;

// i 행과 row 행의 열값이 대각선에 위치하는 절대값이면 안된다.
if (Math.abs(i - x) == Math.abs(y[i] - y[x]))
return false;
}
return true;
}

}

 

 

 

N_Queens.java

0.00MB