프로그래머스, N-Queen

Source: N-Queen

문제 설명

n X n으로 된 정사각형 체스판 안에 n개의 퀸이 서로를 공격할 수 없도록 배치하는 경우의 수 구하기

---

백트랙킹(DFS)로 유명한 문제라 한번 풀어본 적이 있던 문제였다.

2차원 배열로 풀수도 있겠지만 어차피 체스판위의 한 행에는 퀸이 한개밖에 들어갈 수 없으므로 1차원 배열로도 충분히 풀 수 있는 문제이다.

대각선을 판별하는 것만 조금 생각해보면 쉽게 풀 수 있는 문제!

절댓값함수 abs()를 이용해 두 행의 차이가 두 열의 차이와 같다면 같은 대각선에 있는것으로 판별했다

---

코드

#include <bits/stdc++.h>
using namespace std;

int rows[15];
int answer = 0;

bool check(int i){
    for(int c=0; c<i; c++){
        if(rows[i] == rows[c] || abs(rows[i]-rows[c]) == abs(i - c)) return false;
    }
    return true;
}

void dfs(int k, int n){
    if(k==n) {answer++; return;}
    else{
        for(int i=0; i<n; i++){
            rows[k] = i;
            if(check(k)){
                dfs(k+1, n);
            }
            rows[k] = 0;
        }
    }
    return;
}

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