백트래킹 N - Queen

N - Queen

• 백트래킹 -> 모든 경우의 수를 검토하는 것이 아닌 해가 될 가능성이 없는 탐색 대상은 바로 배제

• N-Queen은 n * n 의 그리드 위에서 체스말 퀸이 서로 공격하지 못하는 자리에만 배치하는 문제.

#include <iostream>
#include <vector>

using namespace std;

void printBoard(const vector<vector<int>> &board, int n)
{
    cout << "=======" << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 1)
            {
                cout << "Q ";
            }
            else
            {
                cout << ". ";
            }
        }
        cout << endl;
    }
    cout << "=======" << endl;
}

bool isSafe(const vector<vector<int>> &board, int row, int col, int n)
{
    for (int i = 0; i < row; i++)
    {
        if (board[i][col] == 1)
        {
            return false;
        }   
    } // 상하로 직선에 위치하는지 여부

    for (int i = 1; i <= row; i++)
    {
        if ((col - i >= 0 && board[row - i][col - i]) || (col + i < n && board[row - i][col + i]))
        {
            return false;
        }
    } // 우상단, 좌상단 대각선에 위치하는지 여부 체크

    return true;
}

void solveNQueens(vector<vector<int>> &board, int row, int n)
{
    if (row == n)
    {
        printBoard(board, n);
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (isSafe(board, row, i, n))
        {
            board[row][i] = 1;
            solveNQueens(board, row + 1, n);
            board[row][i] = 0;
        }
    }
}

int main(void)
{
    int n = 4;
    vector<vector<int>> board(n, vector<int>(n, 0));
    solveNQueens(board, 0, n);

    return 0;
}

• 이 문제에서의 관건은 다른 퀸의 위치를 파악하는 데에 있는데, 2차원 배열을 통해 구현하여 행 단위로 반복을 하기 때문에 같은 행에 있는 지 여부는 파악할 필요는 없다.
• 퀸은 대각선과 직선으로 공격이 가능하기 때문에, 같은 열에 있는지 여부와 대각선을 체크해야 하는데,
• 열의 경우 상단에 있는 열만 체크하면 된다.
• 대각선의 경우에도 좌상단, 우상단으로 뻗어나가며 체크하면 된다.