백트래킹

백트래킹(Backtracking)은 가능한 해를 탐색하는 과정에서, 더 이상 유효한 해가 없거나 조건을 만족하지 않는 경우 이전 단계로 되돌아가서 다른 선택을 시도하는 알고리즘입니다. 즉, 한 번 선택한 경로가 더 이상 유효하지 않다고 판단되면, 그 경로를 되돌려 다른 선택을 해보는 방식입니다. 백트래킹은 주로 조합, 순열, 부분집합, 경로 탐색 등의 문제에서 활용됩니다.

백트래킹의 특징:
재귀적 탐색: 가능한 모든 경우의 수를 재귀적으로 탐색하며, 각 단계에서 조건을 만족하는지 검증합니다.
유효성 검사: 진행 중인 선택이 조건을 만족하는지 체크하여, 유효하지 않으면 되돌아갑니다.
가지치기: 조건을 만족하지 않는 경우, 더 이상 탐색하지 않고 다른 경로를 시도합니다.
백트래킹의 예시: N-Queens 문제
N-Queens 문제는 N개의 퀸을 N×N 체스판에 놓을 때, 퀸들이 서로 공격하지 않도록 배치하는 문제입니다. 퀸은 세 가지 방향(가로, 세로, 대각선)으로 공격할 수 있기 때문에, 각 퀸이 서로 공격하지 않도록 배치해야 합니다.

C++ 코드 예시: N-Queens 문제

#include <iostream>
#include <vector>

using namespace std;

// 퀸을 놓을 수 있는지 검사하는 함수
bool isSafe(const vector<int>& board, int row, int col) {
    // 같은 열에 퀸이 있는지 확인
    for (int i = 0; i < row; i++) {
        if (board[i] == col || board[i] - i == col - row || board[i] + i == col + row) {
            return false;
        }
    }
    return true;
}

// N-Queens 문제를 해결하는 함수
bool solveNQueens(vector<int>& board, int row, int N) {
    if (row == N) {
        // 모든 퀸을 배치한 경우
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i] == j) cout << "Q "; // 퀸이 있는 곳에 'Q' 표시
                else cout << ". "; // 퀸이 없는 곳에 '.' 표시
            }
            cout << endl;
        }
        cout << endl;
        return true; // 하나의 해결책을 출력
    }

    bool res = false;
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col; // 퀸을 놓음
            res = solveNQueens(board, row + 1, N) || res; // 다음 행으로 재귀 호출
        }
    }
    return res;
}

int main() {
    int N;
    cout << "Enter the size of the chessboard (N): ";
    cin >> N;

    vector<int> board(N, -1); // board[i]는 i번째 행에 놓은 퀸의 열 위치
    solveNQueens(board, 0, N);
    
    return 0;
}

설명:
isSafe: 주어진 row와 col에 퀸을 놓을 수 있는지 검사하는 함수입니다. 같은 열에 퀸이 있는지, 대각선 방향에 퀸이 있는지 체크합니다.
solveNQueens: 주어진 row에서 퀸을 놓을 수 있는 모든 열을 탐색하며, 백트래킹을 사용하여 모든 가능한 해결책을 찾습니다. 퀸을 놓을 수 있으면 그 위치에 퀸을 놓고, 다음 행으로 재귀적으로 이동합니다.
board: board[i]는 i번째 행에 놓인 퀸의 열 번호를 나타냅니다.
main: 사용자가 입력한 N에 대해 N×N 체스판에 퀸을 놓는 모든 가능한 방법을 출력합니다.