N-Queen / 백트래킹

📌 N-Queen 문제 규칙

 

📌 N-Queen 문제 

 

✅ 구현 코드

*전체 코드

#include <vector>
#include <iostream>

using namespace std;

// 기존 선택된 퀸들의 col과 같으면 false
// 기존 선택된 퀸들의 좌표와 대각선이면 false
bool IsSafe(const vector<vector<int>>& board,const vector<pair<int,int>>& queens, int row, int col)
{
    if (queens.empty()) return true;

    for (auto& p : queens)
    {
        int prev_row = p.first;
        int prev_col = p.second;

        if (col == prev_col || abs(row - prev_row) == abs(col - prev_col)) return false;
    }

    return true;
}

void DFS(vector<vector<int>>& board, vector<pair<int,int>>& queens, const int n, int row, bool& flag)
{
    if (row == n) // 모두 선택되었으면 return
    {
        flag = true;
        return;
    }

    for (int col = 0; col < n; col++)
    {
        if (!IsSafe(board, queens, row, col)) continue;

        queens.push_back({ row,col });
        board[row][col] = 1;

        DFS(board, queens, n, row + 1, flag);

        if (flag) return; // 이미 최적의 해를 찾았으면 return
        queens.pop_back();
        board[row][col] = 0;
    }
}

// board 초기화 및 백트래킹 시작
vector<vector<int>> solveNQueens(const int& n)
{
    vector<vector<int>> board(n, vector<int>(n, 0));
    vector<pair<int, int>> queens; // queen의 좌표 저장
    bool flag = false;

    DFS(board, queens, n, 0, flag);

    return board;
}

// 결과 board 출력
void printBoard(const vector<vector<int>>& board, int n) 
{
    cout << string(n * 2, '=') << 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 << string(n * 2, '=') << endl;
}

int main()
{
    int n;
    cout << "체스판의 N 값을 입력하세요: ";
    cin >> n;

    vector<vector<int>> result_board = solveNQueens(n);
    printBoard(result_board, n);

    return 0;
}

 

🔹 void DFS(vector<vector<int>>& board, vector<pair<int,int>>& queens, const int n, int row, bool& flag)

void DFS(vector<vector<int>>& board, vector<pair<int,int>>& queens, const int n, int row, bool& flag)
{
    if (row == n) // 모두 선택되었으면 return
    {
        flag = true;
        return;
    }

    for (int col = 0; col < n; col++)
    {
        if (!IsSafe(board, queens, row, col)) continue;

        queens.push_back({ row,col });
        board[row][col] = 1;

        DFS(board, queens, n, row + 1, flag);

        if (flag) return; // 이미 최적의 해를 찾았으면 return
        queens.pop_back();
        board[row][col] = 0;
    }
}

• 유망함수 IsSafe에 현재 "board" 상태와 Queen이 배치된 좌표 vector인 "queens", 그리고 현재 퀸을 배치하려는 row와 col을 전달해 해당 위치 좌표가 배치가 가능한 상태인지 판단해 bool으로 반환 받음
• 해당 위치에 배치 못한다면 continue로 다음 좌표를 검색
• 해당 위치에 배치할 수 있다면 "queens"에 현재 좌표를 추가하고 board에 갱신
• 다음 row로 재귀호출
• 만약 모두 선택이 되었다면 퀸의 배치 규칙에 맞게 board가 갱신됨을 의미, flag에 true 값 저장
• 이미 최적의 해를 찾았으므로 더 이상 백트래킹 하지 못하도록 return

 

🔹bool IsSafe(const vector<vector<int>>& board,const vector<pair<int,int>>& queens, int row, int col)

bool IsSafe(const vector<vector<int>>& board,const vector<pair<int,int>>& queens, int row, int col)
{
    if (queens.empty()) return true;

    for (auto& p : queens)
    {
        int prev_row = p.first;
        int prev_col = p.second;

        if (col == prev_col || abs(row - prev_row) == abs(col - prev_col)) return false;
    }

    return true;
}

• 루프를 돌며 현재까지 저장된 모든 퀸의 좌표를 탐색
• col == prev_col: 현재 배치하고자 하는 col과 이전 col이 일치한다면, 수직으로 배치될 수 있기 때문에 false 반환
• abs(row - prev_row) == abs(col - prev_col): 현재 배치하고자 하는 좌표와 이전 좌표가 대각선 상에 위치한다면 fasle 반환
• 모든 검사를 통과하면 배치 가능함을 의미, true 반환

 

🔔 정리

IsSafe 함수에서 이전에 선택된 퀸들의 좌표와 현재 배치하고자 하는 좌표가 대각선 상에 위치해 있는지 판단하는 것을 어떻게 구현해야될지 어려움이 좀 있었던 것 같다.
어떻게 하면 두 좌표가 대각선 상에 있는지 판별할 수 있을지 찾아보다가 아래와 같은 공식을 발견하였다.

abs(row - prev_row) == abs(col - prev_col)

  0   1   2   3
+---+---+---+---+
|   | Q |   |   |  <- (0,1)
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   | * |  <- (2,3)
+---+---+---+---+

위 공식은 (row, col)과 (prev_row, prev_col) 두 좌표가 대각선 상에 있는지 확인하는 조건이다.
두 점 간의 "행(row) 차이"와 "열(col) 차이가 같으면, 이 두 점은 대각선 위에 위치한다.

별표 자리에 만약 퀸을 배치할 수 있는지 확인할 때, (2 - 0) == (3 - 1)  둘의 차이가 같으므로 대각선 상에 위치함을 알 수 있다.