[Back Tracking] 백준 9663번 - N Queen

 

완전탐색을 한다면?

N = 14일때, 14x14의 요소중에서 14개를 뽑는 것이기 때문에

256^14가 된다

제한 시간은 10초(10^9)이기 때문에 초과한다 -> Back Tracking 으로 풀어야 한다

 

2차원 배열에서 알아두면 좋은 점

col이 i, row가 j라고 할 때

 

생각

처음에는 15*15  배열을 만들어 놓고 아래의 규칙에 따라 

퀸이 배치된 칸

퀸이 배치된 칸의 모든 아래 칸들

퀸이 배치된 칸의 왼쪽 대각선 아래 칸들

퀸이 배치된 칸의 오른쪽 대각선 아래 칸들을 모두 false 처리 했다

 

하지만 이렇게 하는 경우 문제가 있다 

빨간색이 파란선과 겹치면서 파란색을 원상복귀 시켜놓는다.

 

이러한 경우를 방지하기 위해서는 각 케이스를 독립적이게 분리할 필요가 있다.

 

2차원 배열에서의 인덱스들의 특징을 생각하여

세가지 경우로 memoization할 배열을 만든다

1. 퀸이 있는 열을 저장하는 배열

2. 퀸이 있는 칸과 열과 행의 인덱스의 합이 같은 값을 저장하는 배열

3. 퀸이 있는 칸과 열과 행의 인덱스의 차가 같은 값을 저장하는 배열

 

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'

int N, cnt;
bool isUsed_col[15];
bool isUsed_rightup[15];
bool isUsed_leftup[15];
// vector<vector<bool> > chess(15, vector<bool>(15, true));

void loop(int col)
{
    if (col == N)
    {
        cnt++;
        return;
    }

    for(int i=0; i<N; i++){

        if(isUsed_col[i] || isUsed_rightup[i+col] || isUsed_leftup[col-i+N-1])
            continue;
        
        isUsed_col[i]=true;
        isUsed_rightup[i+col]=true;
        isUsed_leftup[col-i+N-1]=true;

        loop(col+1);

        isUsed_col[i]=false;
        isUsed_rightup[i+col]=false;
        isUsed_leftup[col-i+N-1]=false;
        
    }

}

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

    cin >> N;
    loop(0);

    cout<<cnt<<endl;
}