[C++/BackTracking/백준] 9663번 N-Queen

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

9663번: N-Queen

---

백트래킹 알고리즘에서 유명한 문제입니다. 체스판에서 퀸은 행,열 대각선을 자유롭게 움직일 수 있습니다. N x N 체스판에서 퀸을 놓아 퀸끼리 서로 공격 할 수 없게 설계하도록하는 모든 경우의 수를 구하는 것이 문제입니다.

 

조건

1. 같은 행과 열에는 퀸이 두 개 이상 존재 할 수 없다. (한 행과 한 열에서는 퀸 한개만 존재 할 수 있습니다)

2. 대각선에서도 퀸은 두 개 이상 존재 할 수 없다.

 

1번 조건에는 col[16]배열을 만들어 Index 번호를 열의 번호, col[index] = value value를 해당 index열에서의 행의 번호 입니다.

ex) col[5] = 3, 5번째 열에 3번째 행에 퀸이 위치 하고 있음

      col[0] = 1, 0번째 열에 1번째 행에 퀸이 위치 하고 있음

      col[3] = 5, 3번째 열에 5번째 행에 퀸이 위치 하고 있음

 

2번 조건은 같은 대각선에 위치하고 있다는 뜻은 퀸 위치 행의 차이와 열의 차이의 크기가 같다는 것입니다.

col[5] = 3 과 col[3] = 5를 예로들자면 행의 차이인 Index번호(5-3) 과 열의 차이인 (3-5)의 크기가 모두 2로 같다는 것입니다. 이 경우 두 개의 퀸은 서로 공격할 수 있는 대각선에 위치하고 있다고 판단 할 수 있습니다.

 

1,2번 조건중 하나만 해당하더라면(or) 퀸은 서로 공격을 하게 됩니다. 따라서 check함수를 이용해 해당 위치에 퀸을 올리지 않도록 코드를 작성합니다.

 

bool check(int level)
{
    for(int i=0;i<level;i++)
    {
        if(level-i==abs(col[level]-col[i])||col[level]==col[i])
            return false;


    }
    return true;
}

여기서 level은 현재 진행하고 있는 행번호를 뜻합니다. 0번째 행부터 퀸을 놓다가 재귀함수를 level 매개변수를 이용해 수행하도록 코드를 작성 했습니다. 현재 진행하고있는 레벨이 체스판의 크기인 N과 같아지면 1,2번 조건을 피해 퀸을 놓는것에 모두 성공한 것이니 answer++을 해줍니다. 그리고 return하여 백트래킹해주어 모든 경우의 수를 찾아냅니다.

 

전체 소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int n;
int col[16]= {-1,};
int answer = 0;

bool check(int level)
{
    for(int i=0;i<level;i++)
    {
        if(level-i==abs(col[level]-col[i])||col[level]==col[i])
            return false;


    }
    return true;
}


void dfs(int level)
{
    if(level==n)
    {
        answer++;
        return;
    }
    for(int i=0;i<n;i++)
    {
        col[level] = i;
        if(check(level)==true)
            dfs(level+1);
            
    }
    
}
int main()
{
    cin>>n;

    dfs(0);

    cout<<answer<<endl;

    return 0;
    
}