[백준 9663번] N-Queen (C++)

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

9663번: N-Queen

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[15];
int N, result = 0;

bool check(int n)
{
    for(int i=0; i<n; i++)
    {
        if(arr[i] == arr[n] || n-i == abs(arr[n] - arr[i])) return 0; //같은 열이거나 대각선이면 불가능
    }
    return 1;
}

void func(int n)
{
    if(n==N) //배치된 퀸의 갯수과 입력과 같으면 경우의 수 증가
    {
        result++;
        return;
    }
    else
    {
        for(int i=1; i<=N; i++)
        {
            arr[n] = i; //퀸 배치
            if(check(n)) func(n+1); //유효하면 다음 행으로 넘어감
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    func(0);
    cout << result;
    return 0;
}

백트래킹의 웰노운 문제이다.

N x N 판이지만, 1차원 배열로도 풀 수 있다는게 핵심인 것 같다.

1차원 배열에 관한 아이디어는 검색을 통해 알 수 있었다.

 

먼저 1차원 배열에 값을 배치하는데 다른 열인 것을 표현하기 위해서 배치하는 값이 행이 바뀔때 마다 달라져야 한다.

이때 배치되는 값이 반복문의 i값인데, 이 값이 어느 열인지 구별하는 역할을 한다.

 

이후 같은 열이나 대각선에 값이 존재하는지 체크를 한다.

체크를 통과한다면 해당 행에 무사히 값이 배치된 것이므로 이제 다음 행으로 넘어간다.

다음행으로 넘어갈때 재귀로 처음에 받은 변수인 n에 +1한 값을 넘겨주는데 이는 행이 같아지는 것을 방지하기 위함이다.

이를 배치된 퀸의 갯수와 입력받은 수와 같아지면 결과값을 증가시킨다.

 

요약하자면 arr[n] = i 가 퀸을 배치하는 것인데, n의 값이 행을 나타내고, i 값이 열을 나타낸다.

1. 해당 행괴 열(n, i)에 값을 배치 

2. 같은 열에 값이 있는지 확인
 - i 값 즉, arr[n]과 같은 값이 현재 열의 길이 만큼 체크했을 때 있는지)
 
3. 대각선에 같은 값이 있는지 확인
 - (x1, y1)의 대각선에 위치하면 -> (x2, y2)  : x1-x2 = y1-y2를 만족한다는 것을 이용
 - n과 i가 열이므로 각각 x1, x2 / arr[n]과 arr[i]가 행이므로 각각 y1, y2
 
4. 배치된 퀸의 갯수와 입력받은 값이 같아질때 까지 반복
 - 같아지면 경우의 수가 1개 추가된 것
 
5. 이렇게 구한 경우의 수 출력