[C++] 9663번 N-Queen - 브루트포스, 백트래킹

#include <iostream>

#define MAX_N 16

using namespace std;

int N;  //체스판의 크기
int cnt;  //가능한 경우의 수
int map[MAX_N];

bool posi(int col)  //col에 퀸을 놓을 수 있는가?
{
    for(int i=1; i<col; i++) {
        if(map[i] == map[col])  //같은 행에 놓여있는가?
            return false;
        if(map[i]+i == map[col]+col)  //같은 대각선 위에 놓여있는가?
            return false;
        if(map[i]+N-i == map[col]+N-col)
            return false;
    }
    return true;
}

void f(int n)  //몇 열에 놓는가?
{
    if(n==N+1)
        cnt++;
    for(int i=1; i<=N; i++) {
        map[n]=i;
        
        if(posi(n))
            f(n+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    f(1);
    
    cout << cnt;
    
    return 0;
}

 

브루트포스 알고리즘이랑 백트래킹이 조금 생소해서 새로운 알고리즘을 공부할 필요가 있었지만 이 문제는 간단해서 빠르게 풀 수 있었던 것 같다. 참고한 사이트는 아래에 있다.

 

 

 

<브루트 포스 알고리즘>

https://hcr3066.tistory.com/26

알고리즘 기법[전체 탐색] - 브루트 포스(brute force)

 

<백트래킹>

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다