[Day 4] 백준 9663 : N-queen

사실 3344번을 풀려고 했지만.. DFS로는 도저히 시간복잡도가 나오지 않는다. 그래서 다른 해법들을 찾아보니 케이스 by 케이스로 분류해서 비교해보는 문제였기 때문에 비교적 작은 값들로 시행하는 9663번을 선택하여 풀게 되었다.

해법 : DFS 

이긴 한데 사실상 시간 제한이 10초이기 때문에 가능한 해법이라고 볼 수 있다. 그만큼 DFS 시간복잡도가 매우 나쁘다. 특히 이 문제에서는 O(n!)의 시간복잡도.. n 최대가 15여서 가능한 풀이라고 볼 수 있다. 

 

어릴 때 이 문제를 처음 봤을 때에는 대각선 분류를 어떻게 해야하는지를 가지고 많은 시간을 고민했었던 것 같다. 그 학습의 결과인지 모르겠지만 대각선 분류는 행 번호(i)와 열 번호(j)를 이용하여 쉽게 할 수 있다.

 

slash 방향의 대각선은 i+j의 값이 일정하고 back slash 방향의 대각선은 i-j의 값이 일정함을 이용하여 해당 대각선을 사용했는지 안 사용했는지 쉽게 판별할 수 있다.

 

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int n;
int v1[200005];
int v2[200005];
int v3[200005];
int back_track[100005];
int flag;
int ans;
void dfs(int cnt) {
    if(cnt==n) {
        ans++;
        return;
    }
    int i;
    for(i=0;i<n;i++) {
        if(flag==1) return;
        if(v1[i]==1 || v2[i+cnt+1]==1 || v3[n+cnt-i]==1) continue;
        //back_track[cnt]=i;
        v1[i]=1;
        v2[i+cnt+1]=1;
        v3[n+cnt-i]=1;
        dfs(cnt+1);

        v1[i]=0;
        v2[i+cnt+1]=0;
        v3[n+cnt-i]=0;
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++) {
        if(flag==0) {
            v1[i]=1;
            v2[i+1]=1;
            v3[n-i]=1;
            back_track[0]=i;
            dfs(1);
            v1[i]=0;
            v2[i+1]=0;
            v3[n-i]=0;
        }
    }
    printf("%d\n",ans);
//for(i=0;i<n;i++) {
    //    printf("%d\n",back_track[i]+1);
    //}
    return 0;
}

---

 번외로 3344번 시도할 때 insert erase 등을 vector를 이용해서 시도해보았다. 효과는 미미했지만.. 

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
int n;
//int v1[200005];
int v2[200005];
int v3[200005];
int back_track[100005];
int flag;
vector <int> A;
void dfs(int cnt) {
    if(cnt==n || flag==1) {
        flag=1;
        return;
    }
    int i;

    for(i=0;i<A.size();i++) {
        vector <int> :: iterator it = A.begin()+i;
        int p = *it;
        //printf("%d ",A.size());
        if( v2[p+cnt+1]==1 || v3[n+cnt-p]==1 || flag==1) continue;
        back_track[cnt]=p;
        //v1[i]=1;
        A.erase(it);
        v2[p+cnt+1]=1;
        v3[n+cnt-p]=1;
        dfs(cnt+1);
        if(flag==1) return;

        A.insert(it,p);

        //v1[i]=0;
        v2[p+cnt+1]=0;
        v3[n+cnt-p]=0;

    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++) {
        A.push_back(i);
    }
    dfs(0);
    for(i=0;i<n;i++) {
        printf("%d\n",back_track[i]+1);
    }
    return 0;
}