그 유명한 N-queen

Is this the real life?
Is this just fantasy?
Caught in a landside,
No escape from reality
Open your eyes,
Look up to the skies and see,
I'm just a poor boy, I need no sympathy,
Because I'm easy come, easy go,
Little high, little low,
Any way the wind blows doesn't really matter to
Me, to me

Mamaaa,
Just killed a man,
Put a gun against his head, pulled my trigger,
Now he's dead
Mamaaa, life had just begun,
But now I've gone and thrown it all away
Mama, oooh,
Didn't mean to make you cry,
If I'm not back again this time tomorrow,
Carry on, carry on as if nothing really matters

백준 N-queen

유명한 백트레킹 문제 N-queen을 풀어보겠다.

이 문제에서 유의해야할 점은 크게 두 가지이다.

1. 행 갱신

2. 시간

 

이 문제를 처음 보고 나는 조금 막막했다. N-queen이 유명하기는 하지만 처음 풀어 본 문제이고, queen을 놓는 것 자체가 복잡한 과정이라고 생각했기 때문이다.

그렇게 2시간, 3시간 고민하고 위키백과에서 N-queen문제의 아이디어를 얻은 후 그 아이디어를 정리하기 위해 이 포스팅을 작성한다. 

 

먼저 힌트를 보자

최고의 힌트다

 

다음 그림과 같은 아이디어를 사용한다.

 

이 아이디어를 이용해서 python 코드를 짜보자

n = int(input())
arry = [-1 for i in range(n)] # arry[x] = x행에 몇 열에 퀸이 놓여있는지
cont = 0
def backtrack(state):
    d = 0
    for i in range(n): # 현재 state 행에서 퀸 위치 열 선택
        pan = 0
        for j in range(state): #어떤 행에서 열이 겹치는 것이 있는가?
            if i == arry[j]:
                pan = 1
        for j in range(state):
            if abs(arry[j]-i) == abs(state-j):
                pan = 1
        if pan == 0:
            arry[state] = i
            backtrack(state+1)
            arry[state] = -1
            d = 1
    if state == n-1 and d == 1:
        global cont
        cont += 1
backtrack(0)
print(cont)

시간 초과다.

 

역시 이런 일에 전문은 C++이다.

내가 쓰던 언어인 C++로 다시 짜보자

구조는 완벽히 동일하다.

#include <iostream>
using namespace std;
int n, cont = 0;
int arry[16] = {0,};
void backtrack(int state){
	int d = 0, pan = 0, i, j;
	for(i = 0; i < n; i++){
		pan = 0;
		for(j = 0; j < state; j++)if(i == arry[j]) pan = 1;
		for(j = 0; j < state; j++)if(abs(arry[j]-i) == abs(state-j))pan = 1;
		if(pan == 0){
			arry[state] = i;
			backtrack(state+1);
			arry[state] = -1;
			d = 1;
		}
	}
	if(state == n-1 && d == 1)cont++;
}
int main(){
	for(int i = 0; i < 16; i++)arry[i] = -1;
	cin >> n;
	backtrack(0);
	cout << cont;
}

시간 개오래 걸리네...