[프로그래머스 2레벨] N-Queen (C++)

#include <string>
#include <vector>

using namespace std;

int answer = 0;
int arr[13];

bool check(int n)
{
    for(int i=0; i<n; i++)
    {
        if(arr[i] == arr[n] || n-i == abs(arr[n]-arr[i])) return 0; //같은 열인지 또는 대각선인지 체크
    }
    return 1;
}

void dfs(int cnt, int n)
{
    if(cnt == n) //퀸 모두 배치
    {
        answer++;
        return;
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            arr[cnt]=i; //cnt, i 좌표에 퀸 배치
            if(check(cnt)) dfs(cnt+1, n); //유효하면 다음 행으로
        }
    }
}

int solution(int n) {
    dfs(0, n);
    return answer;
}

 

퀸의 경우 가로세로 또는 대각선으로 이동이 가능하다.

따라서 위 3가지 방향에 대해 고려를 해야한다.

 

우선 행을 고정시키고, 여기서 열만 바꿔서 퀸을 배치시킬 것이다.

해당 값을 토대로 행을 옮겨 놓을 예정인 값의 유효여부를 판단하고, 가능하면 이어서 dfs 탐색을 이어나간다.

 

행을 고정시켰기에, 행을 탐색할 필요는 없다.

따라서 남은건 같은 열인지, 또는 대각선인지 체크하는 것이다.

반복문을 통해 놓을 예정인 위치가 이미 값이 존재하는 지 여부를 통해 열을 체크한다.

대각선의 경우 행의 차이와 열의 차이가 같은 지 계산식을 통해 대각선 여부를 판별해주면 된다.

이를 모든 퀸이 배치 될때까지 반복하여 가능한 경우를 모두 카운팅 해준다.