백준 9663번:N-Queen

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

9663번: N-Queen

이 문제를 풀 때 일단 퀸은 가로 세로 대각선이면 모두가 공격이 가능하다.

그래서 일단 재귀를 사용해도 반복문으로 같은 열을 반복하면서 재귀를 돌렸고 n의 줄까지 도달하면 탈출하게 했다.

근데 여기서 시간 복잡도가 재귀 돌리면서 열로 n번 행으로 n번 그리고 체크 함수n번을 사용하게 되고 

총 시간 복잡도 O(n^n^2)이라는 어마 무시한 시간 복잡도가 나온다.

다행이 n의 범위가 15까지이고 시간제한이 10초라 아슬아슬하게 돌아가진다.

코드를 보자

#include <iostream>
using namespace std;
bool queen[16][16];
int ans;
bool check(int row,int column,int n){  //열,행,체스판 크기
    for(int i=1;i<=n;i++){
        if(queen[column][i]){    //같은 열에 퀸이 있음
            return false; 
        }
        if(queen[i][row]){             //같은 행에 퀸이 있음
            return false;
        }
        if(column>i&&row>i&&queen[column-i][row-i]){     //왼쪽 위 대각선에 퀸이 있음
            return false;
        }
        if(column>i&&row+i<=n&&queen[column-i][row+i]){     //오른쪽 위 대각선에 퀸이 있음
            return false;
        }
    }
    return true;
} 
void go(int row,int column,int n){ //열,행,체스판 크기,퀸개수
    if(column==n+1){
        ans++;
    }
    for(int k=1;k<=n;k++){
        if(check(k,column,n)){
            queen[column][k]=true;
            go(row,column+1,n);
        }
        queen[column][k]=false;
    }
}
int main(){
    int n;
    cin>>n;
    go(1,1,n);
    cout<<ans;
}