C++:: 프로그래머스 < N-Queen >

전형적인 체스 퀸을 겹치지않고 놓아야하는 dfs 문제이다. 크게 어렵지는 않지만 주의하여 코드를 짜야한다.

#include <string>
#include <vector>
using namespace std;

int answer;

bool isAble(int idx, int cnt, vector<int>& board) {
    for (int i=0; i<cnt; i++) {
        if (board[i] == idx) return false ;// 이전에 둔 퀸이 같은 수평선에 있다면
        if (abs(board[i]-idx) == abs(cnt-i)) return false ;// 이전에 둔 퀸이 대각선에 있다면
        // abs(board[i]-idx) / abs(cnt-i) == 1과 같이쓰면 정수의 버림에 의해 틀렸지만 통과하는
        // 케이스가 생길 수 있으니 주의하자
    }
    return true;
}

void dfs(int cnt, int n, vector<int>& board) {
    if (cnt == n) {
        answer++;
        return ;
    }
    for (int i=0; i<n; i++) {
        if (isAble(i, cnt, board)) {// 퀸이 놓아질수 있는 위치라면
            board[cnt] = i;// 두고
            dfs(cnt+1, n, board);// dfs
        }
    }
}

int solution(int n) {
    vector<int> board(n, 0);
    dfs(0, n, board);
    return answer;
}