# 9663. N-Queen

관련 알고리즘 : 백트래킹

 

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제 풀이

우선, 퀸이 서로를 공격할 수 없게 하기 위해서는 2가지 조건을 만족해야 한다.

1. 퀸이 놓인 자리에서 같은 행 또는 열에 또다른 퀸이 존재해서는 안된다.
2. 퀸이 놓인 자리에서 대각선 위치에 또다른 퀸이 존재해서는 안된다.

1번 조건을 토대로 우리는 n x n 의 2차원 배열을 사용할 필요 없이,

한 열당 1개의 퀸만 존재할 수 있음을 이용해 n개의 일차원 배열만을 이용하여 이 문제를 해결할 수 있다.

 

col[해당 열] = (해당 열에 존재하는 퀸이 어느 행에 위치하는지 - 행에 대한 index)

이런식으로 할당해주면 된다.

 

이후, 한 열씩 퀸을 배치해가면서 N개의 퀸의 배치를 만족할 경우 + 위의 2가지 조건을 만족할 경우

result값을 +1 해주는 백트래킹 기법을 사용한다.

조건을 만족하지 않을 때는 검색 대상에서 제외되므로 해당 문제는 백트래킹을 이용하는 것이 빠른 시간 내에 답을 도출해낼 수 있다.

---

해결 코드 - C++

#include <iostream>
#define MAX 15

using namespace std;

int col[MAX];
int N;
int res = 0; // 결과값

bool check(int row)
{
    // 대각선에 있을 때, 기울기가 1 또는 -1 이므로 행과 열을 좌표처럼 이용, 차이가 동일할 시 대각선에 있다고 판단
    for(int i = 0; i < row; i++)
    {
        if(col[i] == col[row] || abs(col[row] - col[i]) == row - i)
            return false;
    }
    return true; // 조건 만족 시
}

void nQueen(int row)
{
    if(row == N) // N개의 퀸 배치 완료시
        res++;
    else
    {
        for(int i = 0; i < N; i++)
        {
            col[row] = i; // N까지 돌며 퀸 배치
            if(check(row)) // 조건 만족 시 다음 열 퀸 배치
                nQueen(row+1); // 조건 불만족 시 다른 위치에 퀸 배치
        }
    }
}
int main() {
    cin >> N;
    nQueen(0);
    cout << res;
}