[백준] 9663번 N-QUEEN

 

사고력을 키우는데 알고리즘이 좋대서 요즘 계속 풀어보고있는중에 이문제를 만났다.

10초라는 조건때문에 여유가생겨서 그런지 처음 N과 M시리즈를 만났을때보다 쉽게 풀었다.

 

처음에는 X좌표를 0,1,2,...,N으로 해서 이웃하지 않는 순열을 만들어 풀려고했는데,

생각외로 어려웠고 대각방향도 생각해줘야 된다는걸 깨달아 그냥 정공법으로 풀이방향을 바꿨다.

 

같은 행 같은 열에는 무조건 있으면 안되는 점에서 Y에대한 X좌표 vector를 만들고

X좌표에 대해서 루프를 돌면서 비어있는 부분이 나온다면, 재귀를 호출하는 방식으로 풀었다.

 

#include <iostream>
#include <vector>
#include <cmath>


void solve(int N, std::vector<int>& visit, std::vector<int> pointX, int y,int& cnt){
    if(y == N){
        ++cnt;
        return;
    }
    for (int i=0; i<N; ++i){
        if (visit[i] == -1){
            for(int j=0; j<N; ++j){
                if (visit[j] != -1){
                    int delX = abs(i - j);
                    int delY = abs(y - visit[j]);
                    if (delX == delY){
                        visit[i] = -2;
                        break;
                    }
                }
            }
            if (visit[i] != -2){
               pointX[y] = i;
                visit[i] = y;
                solve(N, visit, pointX, y + 1, cnt);        
            }
            visit[i] = -1;
        }
    }
    return;
}
int main(void){
    int n = 0;
    
    std::cin >> n;
    
    std::vector<int> pointX;
    std::vector<int> visit;
    for(int i=0;i<n;++i){
        pointX.push_back(0);
        visit.push_back(-1);
    }
    
    int result = 0;
    solve(n, visit, pointX, 0, result);
    std::cout << result;
    
    
}

[소스코드]

 

맞긴 맞았는데; 시간 5.176초 정도 나온다. 한 1-2초 정도 나오는사람들에 비하면 효율성이 좀 떨어지나보다.

 

-----------------------------------------------------------------------------------------------------------------------------------

글을 쓰면서 보니깐 sovle함수에 pointX를 레퍼런스로 안받고 있었다;; 그래서 메모리가 쌓이고, vector가 계속 복사되는 과정에서 조금더 느렸나 보다. 그래도.. 4.376초. 나중에 반복문으로도 풀어봐야겠다;