(C++) - 프로그래머스(연습문제) : N-Queen

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

코딩테스트 연습 - N-Queen

backtracking문제였습니다.

 

풀이방법

 퀸이 놓일 수 있는 자리라면 dfs를 호출해줍니다. pruning 방식은 well-known입니다.

 

Code

#include <string>
#include <vector>
using namespace std;
int ans, N;
vector <int> board;
int isOk(int tuple) {
    for (int col = 0; col < tuple; col++){
        if (board[tuple] == board[col] || abs(board[tuple] - board[col]) ==  tuple - col )
            return false;
    }
    return true;
}
 
void dfs(int tuple) {
    if (tuple == N) ans += 1;
    else{
        for (int col = 0; col < N; col++){
            board[tuple] = col;
            if (isOk(tuple)) dfs(tuple +1);
        }
    }
}


int solution(int n) {
    ans = 0;
    vector <int> b (n*n,0);
    N = n;
    board = b;
    dfs(0);
    return ans;
}