[python, C++] 백준 9663 : N-queen

9663번: N-Queen (acmicpc.net)

백트래킹 대표문제다.
백트래킹이 무엇인지, 왜 사용하는지 알아보자.

4-queens problem

brute force alogithm : 비효율적임
왜냐? -> 모든 노드를 탐색해야하므로

State space tree

brute force로 해결한다면, DFS로 후보들 사이에서 답을 찾을 수 있겠다.
그러나 앞서 말했듯, 해답이 될 가능성이 전혀 없는 노드의 후손노드까지 모두 검색해야 하므로 비효율적이다.

pruned state space tree

이를 개선한 방법이다.
일단 State space tree 에서 DFS를 사용한다.
여기에서 차이점은 더이상 해답이 나올 가능성이 없는 경우, 더이상 subtree를 확장하지 않고 다시 부모로 돌아간다.

다시 부모로 돌아가는 이 과정을 일겉는 말이 back-tracking이고,
이렇게 더이상 subtree를 만들지 않게하는 것을 pruning이라고 한다.

앞으로 구현할 함수에 필요한 요소다.

• promising : subtree를 만들 수 있는 경우를 지칭한다.
• pruning : 해당 노드의 subtree 검색은 무의미하다는 걸 의미
• 상태 공간 트리에서 DFS를 실시하는데, 유망하지 않은 노드들은 가지쳐서 검색을 하지 않고, 유망한 노드에 대해서만 그 노드의 자식노드를 검색한다.

Steps in backtracking algorithm

해당 알고리즘을 구현할 절차를 알아보자.

우선 pruning을 하지 않을 경우의 pseudo-code다.

• Do DFS
• Check if the node is promising
• If yes, keep searching. If no, do pruning (stop and backtrack)

checknode(node v) {
    node u;
    if(promising(v))
        if (there is a solution at v)
            write the solution;
        else
            for (each child u of v)
                checknode(u);
}

이 방법에서 v=(1,1)일 때, checknode(2,1)는 불릴까?
그렇다. (pruning이 없으므로)

다음은 개선된 backtracking이다.

expend(node v) {
    node u;
    for (each child u of v) 
        if (promising(u))
            if (there is a solution at u)
                write the solution;
            else
                expand(u);
}

이 방법에서 v=(1,1)일 때, checknode(2,1)는 불릴까?
아니다.

문제를 해결하기 위해 필요한 함수

• promising function
  • col[i]를 Qi가 i번째 행에 위치해있는 열이라고 하자.
    • 즉, 1번째 행에 퀸에 4번째에 위치한다면, col[1] = 4가 된다.
  • 만약 같은 행에 있는지 확인하려면 : col[i] = col[k]
  • 만약 같은 대각선에 있는지 확인하려면 : | col[i] - col[k] | = | i-k |
    • 1번째 행에 퀸이 1번째 열에 있고, col[1] = 1
    • 2번째 행에 퀸이 2번째 열에 있다. col[2] = 2
    • 수식에 대입하면, | col[1] - col[2] | = | 1-2 | 라 할 수 있고, 이 수식은 성립한다.

코드로 알아보면 다음과 같다.

python ver.

## col배열에서 i번째 행에 들어갈 퀸이 유효할지 확인하는 함
def promising(i, col) :
    k = 1
    flag = True
    while(k<i and flag):
        if(col[i] == col[k] or abs(col[i]-col[k]) == (i-k)):
            flag = False
        k+= 1
    return flag

def n_queens(i, col) :
    n = len(col) - 1
    if (promising(i, col)) :
        if(i==n):
            print(col[1:n+1])
        else :
            for j in range(1, n+1):
                col[i+1]=j
                n_queens(i+1, col)


# test code
n = 8
col = [0]*(n+1)
n_queens(0,col)

c++ ver.

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ends " "
#define double long double
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cpx;

// ----------------------------------------------

int n;
int ans = 0;
bool promising(int idx, vector<int> &col)
{
    int k = 1;
    bool flag = true;
    while (k < idx && flag)
    {
        // 같은 열에 있거나 같은 대각선에 있는 경우
        if (col[idx] == col[k] || abs(col[idx] - col[k]) == abs(idx - k))
        {
            // 유망하지 않으므로
            flag = false;
        }
        k++;
    }

    return flag;
}

void n_queens(int idx, vector<int> &col)
{

    if (promising(idx, col)) // 유망한 경우
    {
        if (idx == n) // 해답을 찾을 수 있다.
        {
            ans++;
            // for (auto e : col)
            // {
            //     cout << e << ends;
            // }

            // cout << endl;
        }
        else
        {
            // 아니라면 자식을 탐색한다.
            for (int i = 1; i < n + 1; i++)
            { // 해당 행에서 첫번째 열부터 끝까지 돌면서 들어갈 수 있는지 확인하기 위함
                col[idx + 1] = i;
                n_queens(idx + 1, col);
            }
        }
    }
}

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

    cin >> n;
    vector<int> col;
    col.assign(n + 1, 0);

    // n--;
    n_queens(0, col);
    cout << ans;

    return 0;
}

끗!
dfs, back-tracking,, 준내어려워요ㅠ