https://www.acmicpc.net/problem/9663
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
풀이과정
퀸은 체스에서 가장 강력한 기물이다. 체스판에 놓인 퀸 자신으로부터 가로 줄과 세로 줄 그리고 대각선 어디든지 이동할 수 있다. 따라서, 퀸 N개를 서로 공격할 수 없게 놓으려면 같은 가로,세로,대각선 줄에 위치시키면 안될 것이다.
같은 가로 줄에 위치하지 못한다면 퀸 N개를 놓기 위해선 한 개의 가로 줄마다 퀸 1개씩은 무조건 놓아야 한다.
이 점을 유의하여 같은 유형 문제인 N과 M(1)과 동일하게 풀이해보자.
N = 4일 때를 가정해보면 체스판은 아래와 같을 것이다. 이때, 가로 축은 row이고 세로 축은 col이다.
퀸 N개를 놓기 위해선 한 개의 row마다 퀸 1개씩은 무조건 놓아야 한다고 했었다.
row의 col마다 퀸을 한 번씩 놓아보며 조합을 찾는다.
row 1에 퀸을 놓았으니 row 2에도 col을 1씩 증가시키며 퀸을 놓을 자리를 찾는다. row 1에 퀸이 있어 row 2에서는 col 1과 2에는 퀸을 놓을 수 없다. col 3에 놓아보자.
row 3으로 넘어오니 문제가 발생한다. row 3에선 어느 칸에도 퀸을 놓을 수 없다. 따라서 row 1, row 2의 조합에선 N개의 퀸을 놓을 수 없다. 다시 row 2로 돌아와 col 3이 아닌 col 4에 퀸을 놓아본다.
이번엔 row 3에서 col 2에 퀸을 놓는 것이 가능해졌다. col 2에 퀸을 놓고 row 4로 넘어간다.
앗, 가장 밑 row까지 왔지만 어느 칸에도 퀸을 놓을 수 없다. 다시 돌아간다.
row 2에선 마지막 col까지 도달했으므로 row 1까지 돌아간다.
col 2에 퀸을 두고 위에서 했던 단계를 반복한다.
다음은 java로 제출한 풀이 코드이다.
public class Main {
static int N;
static int count = 0;
// row 0 ~ N까지
static int[] select;
// 세로, 대각선 체크 메서드
public static boolean match( int col, int row ){
// 0 번째 row부터 현재 row까지
for( int i = 0; i < row; i++ ){
// i번째 row에 퀸을 둔 col이 현재 col과 같다면
// false
if( select[i] == col )
return false;
// 현재 col+row가 이전에 선택한 퀸 col+row와 같다면
// 오른쪽 위 대각선과 곂침
if( i + select[i] == col+row )
return false;
// row 한 칸이 줄어들 때마다
// row - 1, col - 1 씩 줄어든다면 왼쪽 위 대각선
int temp = row - i;
if( row - temp == i && col - temp == select[i] )
return false;
}
return true;
}
public static void solve( int col, int row ){
// N-1과 같다면 퀸 N개를
// 문제 없이 선택했으므로
// count++
if( row == N-1 ) {
count++;
return;
}
for( int i = 0; i < N; i++){
if(match(i, row+1)) {
select[row + 1] = i;
solve(i, row + 1);
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt( br.readLine() );
select = new int[N];
solve( 0, -1 );
System.out.println(count);
}
}