9663번: N-Queen(백준 C++)

9663번: N-Queen 링크

코드

#include <iostream>
using namespace std;

int col[16] = {0,};
int answer = 0;
int n;

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

void solve(int x){
    if(x > n) answer += 1;
    else{
        for(int i=1; i<=n; i++){
            col[x] = i;
            if(check(x)) solve(x+1);
        }
    }
}
int main() {
    cin >> n;
    solve(1);
    cout << answer;
    return 0;
}

사견

아 진짜 문제 풀면서 울고싶었다 오랜만에
처음에 로직 자체는 맞게 짰는데, 연산자에서 실수 한 거 땜시 계속 머리 잡다가 겨우 풀었는데
시간초과....

시간초과 나게 푸는 방법!

#include <iostream>
using namespace std;

int check[16][16];
int answer = 0;

void init(){
    for(int i=0; i<16; i++){
        for(int j=0; j<16; j++){
            check[i][j] = 0;
        }
    }
}

void pass_Q(int n, int y, int x, int b){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == y) check[i][j] += b;
            else if(j == x) check[i][j] += b;
            else if(abs(y - i) - abs(x - j) == 0) check[i][j] += b;
        }
    }
}

void solve(int n, int y, int x, int cnt){
    int i, j;
    i = y;
    j = x;
    if(cnt == n) answer += 1;
    else{
        for(int i = y; i<=n; i++){
            for(; j<=n; j++){
                if(check[i][j] > 0) {
                    continue;
                }
                else{
                    pass_Q(n, i, j, 1);
                    solve(n, i, j, cnt+1);
                    pass_Q(n, i, j, -1);
                }
            }
            j = 1;
        }

    }
}
int main() {
    init();
    int n;
    cin >> n;
    solve(n, 1, 1, 0);
    cout << answer;
    return 0;
}

느껴지십니까? 코드의 차이가...?
우선 시간초과나게 풀었던 방법의 경우에는, 체스판...이라서 2차원 배열로 만들어놓고 풀었다.
그 다음, Queen을 체스판에 두면, 이제 놓을 수 없는 위치에 1씩 증가시켜주었다.

이렇게 하면 이제 배열의 값이 1 이상인 경우에는 Queen의 이동경로가 겹치는 구간이므로 Queen을 둘 수 없기 때문.
Queen 두면서 Q이 지나갈 수 있는 경로에 1 증가하고...
재귀하고... 재귀 끝나면 다시 두기 전으로 롤백해주고...

이렇게 하면 일단 값은 나온다.

하지만... 시간 복잡도가 엄청나버리게 되는것...

시간초과에 너무 슬퍼서 그냥 해답을 찾아봤다.

근데, 솔직히 안봤으면 못 풀었을거 같다... 이걸 어케 생각하지?

찐 풀이

하나의 열 또는 행에는 하나의 Queen 만이 올 수 있다.

이것이 2차원 배열로 했던 체스판을 1차원 배열로 두는 핵심 Key 이다.

위 그림을 보자.

2차원 배열로 퀸의 위치를 나타낸다고 하면...
bool chess[4][4];
이러한 배열에서, Q의 위치는 chess[0][0] 그리고 chess[1][2] 이렇게 될 것이다.

하지만 1차원 배열로 나타 낼 수 있다.
어떻게?

하나의 열 또는 행에는 하나의 Queen만이 올 수 있다...

즉, chess[0][0] chess[0][1] chess[0][2] chess[0][3]
행이 0인 4개의 위치중 어차피 Queen 하나 들어오면 나머지는 들어갈 수 없기때문에

chess[0] = 0
이렇게 index는 행 또는 열로 두고, 그 배열의 index 값에 Queen의 열 또는 행의 위치값을 넣어주면 된다는 것이다.

이에 따라 1차원 배열로 바꿨을 시 위 그림에서 퀸의 위치는 아래와 같이 나타낼 수 있다.

int chess[4];

chess[0] = 0;
chess[1] = 2;

휴... 백트래킹을 써서 풀긴했었는데 이렇게 최적화에 막히니 가슴이 답답하고 통탄할 나름이다.......
더 열심히 해야지....