프로그래머스 N-Queen [Lv. 2] (C++)

프로그래머스

N * N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 경우의 수를 구하시오.

 

 

풀이 방법

퀸이 서로 공격할 수 없는 위치는 아래와 같은 규칙이 있습니다.

1. 모든 퀸은 Y값이 서로 달라야함

2. 모든 퀸은 X값이 서로 달라야함

3. 퀸에서 다른 퀸으로 이동하는 벡터의 X값의 크기와 Y값의 크기가 달라야함

 

위의 규칙들을 적용시킨다면 체스판의 각 행에는 하나의 퀸이 있으며, 각 열에도 하나의 퀸이 있게 됩니다.

즉, 행이나 열을 기준으로 배치가 가능한 위치를 한줄 한줄 찾아가는 방식으로 풀 수 있겠습니다.

 

---

 

저는 DFS를 이용했습니다.

int DFS(vector<pair<int, int>>& queens, int y, int n)

체스판에 queens배열의 위치에 퀸이 배치 되어 있을 때, 나머지를 채울 수 있는 경우의 수를 뱉게 됩니다.

y값은 탐색할 y의 위치를 뜻 하며 넘겨받은 y값에서 x값을 순회하여 배치 위치를 찾게됩니다.

 

ex) queens = {{0, 1}}, y = 1, n = 4

탐색 범위 -> [1, 0] ~ [1, 3]

다음 DFS) queens = [[0, 1], [1, 3]],  y = 2,  n = 4

탐색 범위 -> [2, 0] ~ [2, 3]

 

vector<pair<int, int>> queens;
return DFS(queens, 0, n);

DFS의 시작은 빈 배열부터 시작합니다.

 

 

for (int x = 0; x < n; x++)
{
    bool flag = true;
    for (auto& queen : queens)
    {
        if (x == queen.second || y == queen.first ||
            abs(x - queen.second) == abs(y - queen.first)) 
        {
            flag = false; 
            break;
        }
    }

배치 해야할 y값은 이미 정해져 있는 상태이기 때문에 x값을 순회하며 배치가 가능한지 체크합니다.

 

if (flag)
{
    queens.push_back({y, x});
    answer += DFS(queens, y + 1, n);
    queens.pop_back();
}

배치가 가능하다면 quuens 배열에 위치 값을 추가하고 DFS를 호출합니다.

다른 경우의 수를 찾기 위해 다시 pop_back()함수를 호출 했습니다.

 

if (queens.size() == n)
    return 1;

queens 배열의 크기가 n과 같다면 1을 반환하여 배치의 가능 여부를 보고합니다.

이후 반환된 1을 모아서 제출하면 마무리됩니다.

 

정답 코드

#include <string>
#include <vector>

using namespace std;

int DFS(vector<pair<int, int>>& queens, int y, int n)
{
    if (queens.size() == n)
        return 1;
    
    int answer = 0;
    for (int x = 0; x < n; x++)
    {
        bool flag = true;
        for (auto& queen : queens)
        {
            if (x == queen.second || y == queen.first ||
                abs(x - queen.second) == abs(y - queen.first)) 
            {
                flag = false; 
                break;
            }
        }
        
        if (flag)
        {
            queens.push_back({y, x});
            answer += DFS(queens, y + 1, n);
            queens.pop_back();
        }
    }
    
    return answer;
}

int solution(int n) {
    vector<pair<int, int>> queens;
    return DFS(queens, 0, n);
}