[C++] 프로그래머스 N-Queen 재귀

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void BackTracking(int y, int n, vector<vector<int>> visited);

int solution(int n) {
    vector<vector<int>> visited(3); //0 x, 1 left, 2 right
    BackTracking(0, n, visited);

    return answer;
}

void BackTracking(int y, int n, vector<vector<int>> visited)
{
    if (y == n)
    {
        answer++;
        return;
    }

    for (int x = 0; x < n; x++)
    {
        bool next = false;
        //x와 대각선좌표에 해당되는지 판단
        for (int j = 0; j < 3; j++)
        {
            for (auto a : visited[j])
            {
                switch (j)
                {
                case 0:
                    if (a == x) next = true;
                    break;
                case 1:
                    if (a == y + x) next = true;
                    break;
                case 2:
                    if (a == x - y + n - 1) next = true;
                    break;
                }
            }
        }

        if (next == false)
        {
            visited[0].push_back(x);
            visited[1].push_back(y + x);
            visited[2].push_back(x - y + n - 1);
            BackTracking(y + 1, n, visited);
            visited[0].pop_back();
            visited[1].pop_back();
            visited[2].pop_back();
        }
    }
}

풀이

1. 현재 위치에서 퀸이 있을 수 있는지에 대한 조건인 (x좌표, 대각선좌표들)에 해당되는지 확인해준다.
2. 대각선은 현재위치가 위쪽에서 아래로 가는 대각선(↘)은 x+y
   아래에서 위로 향하는 대각선은 x - y + n - 1로 계산해준다.
3. 해당된다면 현재 x에 있는 것은 모두 퀸을 배치할 수 없으니 y를 한 칸 전진한다.
   또한 현재 x좌표와 대각선좌표들을 저장해준다.
4. y가 n이 된다면 완성된 것이므로 개수를 추가해준다.
5. 다시 함수가 종료되면 해당 좌표를 놓은 것이 취소가 되어야 하므로 pop_back해주어 저장된 것을 없애준다.

 

 

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen