[백준] 9663번 N-Queen C++

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

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

접근방식 및 풀이

백트래킹을 통해 모든경우를 탐색하고 가지치기하며 해를 구해나간다.

1. 1번째 행부터 각 행에 대해 각각 1~n까지의 칸에 퀸이 있는 모든 경우를 탐색한다.

2. 탐색 중 해당칸에 퀸을 놓는 것이 허용되면 놓고 그렇지 않으면 리턴한다. -> 가지치기

3. pos가 n+1까지 다다르면 n개의 퀸을 다 규칙에 맞게 놓게된것을 의미하므로 이때 카운트를 한다.

 

#include <iostream>

using namespace std;

int n, count=0;
int b[15]={0}; // max_N : 14

bool check(int pos){
    for (int i = 1; i < pos; i++) {
		if (b[pos] == b[i] || pos - i == abs(b[pos] - b[i])) {
			return false;
		}
	}
	return true;
}

void bt(int pos){
    if(pos==n+1){
        count++;
        return ;
    }
    
    for(int i=1; i<=n; i++){
        b[pos]=i;
        if(check(pos)==true){
            bt(pos+1);
        }
    }
    
    return ;
}

int main(){
    cin >> n;
    bt(1);
    printf("%d", count);
    return 0;
}

 

느낀점

처음에 2차원 배열로 접근했다. n이 13일때 너무 복잡도가 커지길래 해결방법을 계속 생각해보았다. 더 효율적인 가지치기 방법이 있나에만 집중하다가 결국 해답을 보았고 1차원 배열로도 풀이가 가능하다는 것을 알게 되었다. n-queen풀이의 판이 2차원인 것을 곧이곧대로 받아들인 탓에 유연한 사고를 못한게 아쉬웠다.