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

https://school.programmers.co.kr/learn/courses/30/lessons/12952

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

내 풀이

N-Queen은 백트래킹의 대표적인 예제라고 한다.

백트래킹을 공부하면서 다시 풀어봤는데, 조건에 따라 DFS를 진행하다가 조건에 맞지 않는 경우라면 처음부터 조건에 따라 DFS를 진행하는 느낌이었다. 백트래킹 공부할 수 있어 좋은 문제였다.

#include <string>
#include <vector>

using namespace std;

int N;
int answer = 0;
int queen_col[13]; // 1차원 배열로 표시

bool check(int row)
{
    // 같은 행, 열과 대각선상에 놓일 수 없다.
    for(int i = 0; i < row; ++i)
    {
        if(queen_col[row] == queen_col[i] 
           || row-i == abs(queen_col[row]-queen_col[i]))
            return false;
    }
    return true;
}

void nqueen(int row)
{
    // 열 개수와 queen 개수 같으면 찾기 완료
    if(row == N)
    {
        ++answer;
        return;
    }
    
    for(int i = 0; i < N; ++i)
    {
        // 1. row 행, i번째 열에 queen 놓아보기
        queen_col[row] = i;
    
        // 2. 검증하기
        if(check(row))
        {
        // 3. 다음 퀸 놓기
            nqueen(row+1);
        }
    }

}

int solution(int n) 
{
    N = n;
    nqueen(0);
    return answer;
}