본문 바로가기
<알고리즘 문제풀이&연습>/[C++] 백준

[백준 9663] N-Queen(DFS 깊이우선탐색)

by 사용자 BlockDMask 2017. 10. 15.
반응형
  • 안녕하세요  BlockDMask 입니다.

  • 오늘은 다들 학교에서 한번쯤 들어본 N-Queen 체스 문제를 풀어보았습니다.

  • 은근 신경써야 하는 부분이 많더군요;;;;

0. 제목

  • 백준 9663 N-Queen (DFS)

  • BOJ 9663 N-Queen (DFS)

1. 문제 설명

  • N-Queen 문제는 체스판 크기가 N x N 인 체스판 위에 퀸 N개를 서로 공격하지 못하도록 배치하는 
    총 방법의 수를 구하는 프로그램을 작성하는 문제입니다.

  • 정수 n이 입력으로 들어옵니다. (1<= N < 15)

  • 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력합니다.

2. 풀이 과정


맨 첫행의 첫 번째 부터 퀸을 놓습니다.
-> 그 다음 행에서 위의 행의 퀸과 일치 하지 않는 맨 왼쪽 열에 퀸을 놓습니다.
-> n 번째 열까지 도달한다면 전체 count 를 하나 더합니다.
-> 그렇지 않다면 다시 백트랙킹합니다.


배열 arr은 열의 개수 를 뜻합니다.

같은 열(세로)라인에 Queen이 존재하는지 검사합니다.



d1은 오른쪽 위를 향하는 대각선입니다.

이들 대각선들은 y, x값을 더하면 일정한 값으로 유지 되는 것을 알 수 있습니다.


4*4 배열을 예로 들면

[0,0][0,1][0,2][0,3]

[1,0][1,1][1,2][1,3]

[2,0][2,1][2,2][2,3]

[3,0][3,1][3,2][3,3]


이런식으로 색별로 y+x 가 일정한 수를 유지합니다.

n x n의 배열에서 대각선의 갯수는 2*n -1 개가 존재합니다.




d2은 오른쪽 아래를 향하는 대각선입니다.

이들 대각선들은 y-x [앞-뒤] 값이 일정한 값으로 유지 되는 것을 알 수 있습니다.


4*4 배열을 예로 들면

[0,0][0,1][0,2][0,3]

[1,0][1,1][1,2][1,3]

[2,0][2,1][2,2][2,3]

[3,0][3,1][3,2][3,3]


이런식으로 색별로 y-x 가 일정한 수를 유지합니다.

n x n의 배열에서 대각선의 갯수는 2*n -1 개가 존재합니다.

배열의 index에 음수가 없으므로 (n-1) + (y-x) 의 값을 element로 받아줍니다.


3. 코드


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
//https://www.acmicpc.net/problem/9663
//BOJ_9663_N-Queen
 
#include<iostream>
using namespace std;
 
int n;
bool *arr; //열의 개수 (세로 개수)
bool *d1;  //오른쪽 위를 향하는 대각(각 자리의 합) = (2n - 1)개
bool *d2;  //오른쪽 아래를 향하는 대각{(n-1)+(행-열) 로 구분}
int result;
 
 
void Solution(int y){
    if(y>=n) result++;
 
    for(int i=0; i<n ; i++){
        if(arr[i]) continue//arr[i]가 존재하면 continue;
        if(d1[y+i] || d2[n-1+(y-i)]) continue//대각선상에 존재하면 continue;
 
        arr[i] = d1[y+i] = d2[n-1+(y-i)] = true;  //체크하고
        Solution(y+1);  //아래 행으로 넘어감
        arr[i] = d1[y+i] = d2[n-1+(y-i)] = false//백트랙킹 조건
    }
}
 
int main(void){
    cin >> n;
 
    arr = new bool[n];
    d1 = new bool[2*n-1];
    d2 = new bool[2*n-1];
    Solution(0);
    cout << result << endl;
    
    delete[] arr;
    delete[] d1;
    delete[] d2;
    return 0;
}
 
cs


4. 인증


문제 출처 - https://www.acmicpc.net/problem/9663

감사합니다. 하트 꾹꾹 부탁드립니다.!

반응형

댓글0