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

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

프로그래머스

 

N-Queen 문제는 대표적인 백트래킹 문제이다. 

이때 백트래킹은 

모든 가능한 경우를 탐색하기 위해 사용하는 기법 중 하나로, 탐색 과정에서 조건을 만족하지 않는 경우를 미리 배제함으로써 탐색 효율을 높인다. 

 

이문제를 백트래킹으로 푸는 과정은 다음과 같다.

 

• 체스판의 각 열에 대해 퀸을 한 행씩 배치한다.
• 퀸을 배치할 때마다 현재 퀸이 다른 퀸과 공격하지 않는지 확인한다.
• 만약 조건을 만족하지 않는다면 해당 배치를 포기하고, 다른 행에 퀸을 배치해 본다. - 백트래킹
• 모든 퀸을 배치할 수 있다면 경우의 수를 추가해준다.
• 모든 가능한 배치를 탐색한 후 경우의 수를 반환 

abs(positions[i] - col) == abs(i - row) -> 1이나 -1 방향에 퀸이 있는지 확인 -> 대각선

#include <string>
#include <vector>
#include <cmath>

using namespace std;

bool isValid(const vector<int>& positions, int row, int col) {
    for (int i = 0; i < row; ++i) {
        // 같은 열에 퀸이 있는지, 또는 대각선에 퀸이 있는지 확인
        if (positions[i] == col || abs(positions[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

void solveNQueens(int n, int row, vector<int>& positions, int& answer) {
    if (row == n) {
        // 모든 퀸을 배치한 경우
        ++answer;
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isValid(positions, row, col)) {
            positions[row] = col;
            solveNQueens(n, row + 1, positions, answer);
            positions[row] = -1; // 백트래킹
        }
    }
}

int solution(int n) {
    int answer = 0;
    vector<int> positions(n, -1); // 각 열에 대한 퀸의 위치
    solveNQueens(n, 0, positions, answer);
    return answer;
}