Level 2. N-Queen

Level 2. N-Queen

 

 

백트래킹(Backtracking)과 DFS(Depth-First Search)

 

DFS를 시도하다가 무조건 시간 초과가 날 것 같아서 다른 방법을 찾아봤더니 백트래킹이 있었다.

• 익히 들어봤지만 이름이 뭔가 어려울 것 같아서 공부하지 않고 있었는데, 그닥 어려운 개념은 아니었다.

 

간단히 말하면 조건부 DFS이다.

• DFS는 조건에 상관 없이 모든 경우를 탐색하기 때문에 시간이 많이 걸린다.
• 백트래킹은 조건을 확인해, 유망한(Promising) 경우 계속 탐색하고, 유망하지 않은(Non-promising) 경우는 더 탐색하지 않는다.
• 이렇게 조건을 확인해 더 탐색하지 않는 것을 가지치기(Pruning)라고 한다.

 

보드가 2차원이다 보니 2차원 배열을 써야 할 것 같지만, 1차원으로도 해결할 수 있다.

• 1차원 배열의 인덱스는 행 번호를 의미하고, 값에는 해당 행에서의 퀸이 있는 열 번호를 저장한다.

 

백트래킹을 활용하면, DFS를 수행하면서 현재 위치에 퀸을 놓을 수 있는 경우는 더 탐색하고, 그렇지 않으면 더 탐색하지 않는다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool canQ(vector<int>& board, int row, int col)
{
    for (int r = 0; r < row; r++)
        if (board[r] == col)
            return false;
        else if (abs(row - r) == abs(col - board[r]))
            return false;

    return true;
}

int rDFS(vector<int>& board, int row)
{
    size_t n = board.size();

    if (n <= row)
        return 1;

    int result = 0;

    for (int col = 0; col < n; ++col)
    {
        if (canQ(board, row, col))
        {
            board[row] = col;
            result += rDFS(board, row + 1);
        }
    }

    return result;
}

int solution(int n)
{
    vector<int> board(n, 0);

    return rDFS(board, 0);
}