티스토리 뷰

백준 (BOJ)/백트래킹

백준)9963-N-Queen

플레지 2019. 5. 1. 18:56

문제 링크: https://www.acmicpc.net/problem/9663

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

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

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

입력

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

출력

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

 

 

풀이

먼저 문제를 풀기 전 알아야 할 규칙이 있다. 퀸은 동서남북 그리고 대각선 방향 양방향 모두 이동이 가능하다.

이 조건에 만족하는 퀸 8 분이 모두 위치하기 위해서는 각 퀸 분들은 2개 이상의 퀸이 같은 행 또는 열 또는 대각선에 존재하면 안 된다.  이 퀸들이  해당하는 위치는 배열을 이용하여 받았다. 행을  i 열을 j  대각선 은  / 또는 \ 이 있다. 대각선 친구들은 [ i+ j ]  그리고    [ i - j + N]으로 나타 낼 수 있다.

각 행 또는 열  /  또는 \ 를 방문한 적이 있다면 1 처리를  해주면 된다.

다 돌았는데 cnt 값이 만약 N 이면 모든 퀸을 겹치는 부분 없이 배치해준 것이므로 ans 값을 1 증가시켜준다.

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
#include<iostream>
using namespace std;
int r[15];
int l[15];
int lx[30];
int rx[30];
int N;
int ans;
void dfs(int i , int cnt)
{
    int j;
    
    if(cnt == N)
    {
        ans++;
        return ;
    }
    
    
    
    for(j=0 ; j< N ; j++)
    {
        if(  !r[i] && !l[j] && !lx[i+j] && !rx[ i - j + N ]  )
        {
            r[i] = l[j]  = lx[i+j] = rx[ i - j + N ] = 1 ;
            dfs(i+1 , cnt +1);
            r[i] = l[j]  = lx[i+j] = rx[ i - j + N ] = 0 ;
                    
        }
    
    }
}
 
 
int main()
{
    cin >> N;
    
    dfs(0,0);
    
    cout << ans ;
    return  0 ;
}
 
cs

 

'백준 (BOJ) > 백트래킹' 카테고리의 다른 글

백준)1759-암호 만들기  (0) 2019.05.01
백준)1987-알파벳  (2) 2019.04.29
백준)6603-로또  (0) 2019.04.28
댓글