9663 N-Queen (백트래킹) [Gold IV]

9663번: N-Queen (acmicpc.net)

 

N * N크기의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓을 수 있는 경우의 수를 찾는 문제입니다.

 

풀이 방법

경우의 수를 찾는 문제여서 점화식을 구하는 문제라 생각할 수도 있습니다만

시간제한이 10초인 것을 보면 브루트포스 알고리즘이라는 것을 알 수 있겠습니다.

 

이 문제를 풀기 위해서는 퀸을 놓을 수 없는 위치의 조건을 생각해볼 필요가 있습니다.

퀸은 8개의 방향으로 원하는 만큼 이동할 수 있습니다.

즉 같은 x선에 있으면 안되고 같은 y선에 위치하면 안됩니다.

또한 대각선 방향도 위치할 수 없습니다. 

// (상 하 좌 우) 방향
if (dir.x * dir.y == 0)
        return false;

// 대각 방향
if (abs(dir.x) - abs(dir.y) == 0)
        return false;

코드로 표현하면 위와 같이 표현이 가능합니다.

상 하 좌 우 단방향으로 이동할 때는 x, y둘 중 하나가 무조건 0인 상태인 것을 이용했으며

대각선 방향의 경우 x, y의 길이가 무조건 같다는 점을 이용하여 절대값을 빼는 방식으로 찾았습니다. 

 

정답 코드

struct Pos
{
    int x;
    int y;

    void operator+=(Pos other) {
        x += other.x;
        y += other.y; 
    }

    Pos operator -(Pos other) {
        Pos result;
        result.x = x - other.x;
        result.y = y - other.y;

        return result;
    }
};

위치값 관리를 보기 좋게 하기 위해 만든 구조체입니다.

 

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

    cin >> N;
    for (int i = 0; i < N; i++)
    { 
        vector<int> v;
        v.push_back(i);
        result(v);  
    } 

    cout << Count;
}

 

이차원 배열을 사용하지 않고 1차원 배열을 이용했습니다.

 y = 0 , x = 4일 경우는 0번째 인덱스에 4를 넣어주었습니다. 

이렇게 코딩하면 N^2번의 탐색을 할 필요없이 N번만 하면 된다는 장점이 있습니다.

 

void result(vector<int> v)
{
    if (v.size() == N) {
        Count++; 
        return;
    }

    for (int j = 0; j < N; j++)
    {
        if (Check(v, Pos{ int(v.size()), j})) 
        {
            vector<int> nextV = v;
            nextV.push_back(j); 

            result(nextV);  
        }
    }
}

모든 경우의 수에 대해서 구해야하기 때문에

vector를 복사하고 다음 위치를 넣어 재귀함수로 넣어주었습니다.

 

bool Check(vector<int>& v, Pos pos)
{  
    for (int i = 0; i < v.size(); i++)
    {
        Pos prev = Pos{ i, v[i] };
        Pos cur = pos;

        Pos dir = prev - cur;

        // (상 하 좌 우) 방향
        if (dir.x * dir.y == 0)
                return false;

        // 대각 방향
        if (abs(dir.x) - abs(dir.y) == 0)
                return false;
    }
    return true;
}