BOJ 9663 N-queen [C++]

처음 글을 써본다.

브루트포스 알고리즘. 무식하게 푼다는 뜻이다. 근데 정말 무식하게 풀어서 이문제를 3시간 걸렸다.

먼저 체스를 해본적이 없어서 퀸이 어떻게 움직이는지 알아봤다.

무식하게 순서만 다른 같은 경우의 수를 확인을 못했다.

그리고 또 무식하게 O(n^2)짜리를 재귀함수 안에 넣었다.

이 문제는 위에서 한 행씩 내려가면서 퀸을 놓을 위치 한개씩을 선택하면 된다. 

그 과정에서 두 대각선 방향과 이미 방문된 열인지 체크해주면 된다. 

 

이 과정을 좀 쉽게 하기 위해 수학을 곁들이면

좌표평면에서 x,y절편이 같도록 기울기가 -1인 직선을 그으면 그 직선 위 모든 좌표의 x,y좌표의 합은 일정하다.

이 원리를 적용해 대각선 방문 여부를 쉽게 저장할 수 있다.

 

아래는 시행착오가 담긴 무식한 코드 + 디버깅이다.

#include <bits/stdc++.h>
#define INF 987654321

using namespace std;

int cnt=0,n;

bool visit1[31] = { false }, visit2[31] = { false }, visit4[15] = { false };


void dfs(int t, int si) {

    if (t == n) {
        cnt++;

        return;
    }


    for (int j = 0; j < n; j++) {

        if (!visit1[si+j] && !visit2[n-1-j+si] && !visit4[j]) {

            visit1[si + j] = true;
            visit2[n - 1 - j + si] = true;
            visit4[j] = true;

            dfs(t + 1, si+1);

            visit1[si + j] = false;
            visit2[n - 1 - j + si] = false;
            visit4[j] = false;
        }

    }
    

    return;

}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    dfs(0, 0);
    cout << cnt;


    return 0;

}

 

그리고 이 아래는 최종 제출한 정답이다. 이 문제의 질문 게시판을 보는데 고수분들이 참 많이 계신것 같다.

#include <bits/stdc++.h>
#define INF 987654321

using namespace std;

int cnt=0,n;

bool visit1[31] = { false }, visit2[31] = { false }, visit3[15] = { false }, visit4[15] = { false };


//void dfs(int t,int si, vector<pair<int,int>> reco) {
void dfs(int t, int si) {

    if (t == n) {
        cnt++;

        /*for (int i = 0; i < reco.size(); i++) {
            cout << reco[i].first << " " << reco[i].second << "  ";
        }
        cout << "\n";*/

        return;
    }

    for (int i = si; i < n; i++) {


        for (int j = 0; j < n; j++) {


            if (!visit1[i+j] && !visit2[n-1-j+i] && !visit3[i] && !visit4[j]) {

                visit1[i + j] = true;
                visit2[n - 1 - j + i] = true;
                visit3[i] = true;
                visit4[j] = true;

                //reco.push_back({ i,j });
                //dfs(t + 1,i,reco);
                //reco.erase(reco.end() - 1);

                dfs(t + 1, i);

                visit1[i + j] = false;
                visit2[n - 1 - j + i] = false;
                visit3[i] = false;
                visit4[j] = false;
            }

        }
    }

    return;

}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    //vector<pair<int, int>> temp;
    //dfs(0, 0, temp);
    dfs(0, 0);
    cout << cnt;




    return 0;

}