[백준] 9663번 N-Queen C++ 문제풀이

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제 풀이

백트래킹을 이용해 문제를 해결했다.

Promising 이란 함수를 만들어서 체스판에 놓여진 위치가 유망한지 아닌지를 판단했다.

Promising에서는 같은 column인지, 같은 대각에 있는지를 확인했다

같은 행인것을 확인 안 한 것은 행마다 하나의 Queen을 놓는 식으로 코드를 작성해 같은 행인지에 대해서는 확인할 필요가 없다. 

알고리즘 수업때 배운 내용이여서 큰 문제 없이 코드를 작성했다.

 

소스코드

#include <iostream>
using namespace std;

int N;
int col[16];
int cnt = 0;

bool promising(int idx) 
{
    int k = 0;
    bool swt = true;

    while (k < idx && swt) {
        if (col[k] == col[idx] || abs(col[idx] - col[k]) == idx - k)
            return false;
        k++;
    }
    return true;
}


void queens(int row) {
    if (row == N)
        cnt++;
    else
    {
        for (int i = 0; i < N; i++)
        {
            col[row] = i; 
            if (promising(row)) 
                queens(row + 1);
        }
    }
}

int main() {
	cin >> N;
	queens(0);
	cout << cnt << '\n';
}