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

• 안녕하세요  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. 코드

//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;
}
 

4. 인증

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

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