[백준 9663] N-Queen C++

문제 이해하기

• 같은 행, 같은 열, 대각선에 겹치면 안됨

소스코드

#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;

int col[110];
int N;
int result = 0;

bool promising(int i)
{
    int k=0;
	
	while (k<i) {
		if (col[i] == col[k] || abs(col[i] - col[k]) == i-k)
			{ return  false; }
		k++;
	}
	return true;
}
void queens(int i)
{
    if(i == N)
        result++;
    else {
        for(int j=0; j<N; j++) {
            col[i] = j;
            if(promising(i))
               queens(i+1);
        }
    }
}

int main()
{
    cin>>N;

    queens(0);

    cout<< result;

    return 0;
}

성능을 위해 2차 배열보다 1차 배열 이용.

처음에 queens(1)로 했다가 값이 다르게 나왔다. 나는 행과 열이 1부터 시작하므로 상관없을거라 생각했다.
생각해보니 queens(1)로 놓으면 마지막열이 n이 된다. 그렇게 되면 n이 유망한지 판단할 queens 함수 안에 else문을 지나치지 못하게 되므로 값이 적게 나온 것이다.