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

문제 링크 : www.acmicpc.net/problem/9663

 

 

단순 백트래킹 문제다.

그냥 무작정 다 배치한 다음 확인을 하면 n^n이라는 어마어마한 시간복잡도가 나오게 된다.

결국 백트래킹을 사용해야한다.

 

 

 

<전체적인 알고리즘>

1. 한 줄씩 queen을 놓아본다.

2. queen을 놓을 수 없는 상황이오면 바로 돌아간다.(백트래킹)

 

 

 

 

<전체코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<iostream> #include<vector>   using namespace std;   vector<pair<int, int>> queen; int n; int result = 0;   bool can_exist(int x,int y)  //해당 위체에 queen놓을 수 있는지 {     for (int i = 0; i < queen.size(); i++)     {         int x2 = queen[i].first;         int y2 = queen[i].second;         if (x == x2 || y == y2 || abs(x - x2) == abs(y - y2))return false;         //대각선이나 직선에 다른 queen이 있으면 존재 불가능, false 반환     }     return true; }   void dfs(int x) {     if (x < 0)     {         result++;         return;     }       for (int i = 0; i < n; i++)     {         if (can_exist(x, i))  //놓을 수 있으면         {             queen.push_back(make_pair(x, i));  //놓고             dfs(x - 1);   //그 다음 줄 ㄱㄱ             queen.pop_back();          }       } }     int main() {     cin >> n;       dfs(n-1);       cout << result << "\n";       return 0; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.