[Algorithm] Baekjoon 9663번 : N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

int queensCol[16]; // queensCol[row] -> row에 위치한 열위치.
int targetCount = 0;
int result = 0;
 
bool check(int curRow,int curCol)
{
    for (int i = 0; i < curRow; i++) // 이전 행들 탐색.
    {
        if (queensCol[i] == curCol) return false; // 이전 퀸들이 같은 열인지 체크.
        if (abs(curRow - i) == abs(curCol - queensCol[i])) return false; // 대각선상에 있는지 체크.
    }
 
    return true;
}
 
 
void PlaceQueen(int row, int count) // 행, 카운트
{
    if (count == targetCount)
    {
        result++;
        return;
    }
 
    for (int col = 0; col < targetCount; col++) // i는 열
    {
        if (check(row,col)) // i번째 열의 index의 행에다가 배치해보기.
        {
            queensCol[row] = col;
            PlaceQueen(row + 1, count + 1); // 다음 행 진입.
            queensCol[row] = 11111111;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
 
    cin >> n;
    targetCount = n;
 
    PlaceQueen(0,0); // 첫번째 행부터 시작.
 
    cout << result;
}

 

백트래킹 대표문제인 N-Queen.

N * N의 크기의 체스판에 N개의 퀸을 놓는 경우의 수들을 구하는 문제이다.

2차원배열의 체스판이기 때문에 퀸의 위치를 2차원배열로 저장해놓기도 하지만, 1차원으로도 표현이 가능하다.

왜냐하면 체스판의 특정위치에 뭐가 있느냐..가 중요한게 아니기 때문이다.

어차피 퀸은 한 행에 반드시 1개씩만 존재하기 때문에 1차원배열로도 충분히 코드짜기가 가능하다.

행을 인덱스로 사용하고 해당원소에 퀸의 열값을 집어넣으면 각 행의 퀸의 위치를 설명 가능하다.