백준 9663 (n-Queen) / C++

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

9663번: N-Queen

> 풀이 

백트래킹 입문 문제로 유명한 n-Queen 문제입니다.

 

백트래킹은 dfs방식인데, dfs는 스택을 통해 구현이 됩니다.

 

함수의 재귀 호출 또한 스택의 일종인 점 생각하시면 이해하시는데 편할 겁니다.

#include <stdio.h>
#include <stdlib.h>

bool promising(int n);
void nQueen(int n);

int queen[15];
int num, cnt;

int main(void) {
        scanf("%d", &num);

        nQueen(0);
        printf("%d", cnt);
        return 0;
}

bool promising(int n) {
        for (int i = 0; i < n; i++) 
                if (queen[i] == queen[n] || abs(queen[i] - queen[n]) == abs(i - n)) 
                        return false;
        return true;
}

void nQueen(int n) {
        if (n == num) cnt++;
        else {
                for (int i = 0; i < num; i++) {
                        queen[n] = i;
                        if (promising(n)) nQueen(n + 1);
                }
        }
}

(개발 환경 : vs code)