프로그래머스 N-Queen dfs backtracking C++

 

풀이 방법

 

'하나의 열 or 하나의 행에는 반드시 하나의 퀸만 놓을 수 있다' 라는 점을 통해 풀이하면 된다.

 

int row[12] : 각각의 행에 몇번째 열이 매칭되는지 (퀸이 놓이는지) 를 나타낸다

 

void dfs(int rowNum){
    if (rowNum==N){
        Answer++;
        return;
    }
    for (int i=0;i<N;i++){
        row[rowNum] = i;
        if (check(rowNum)){
            dfs(rowNum+1);
        }
        row[rowNum] !=i;
    }
}

행에 for문을 통해서 하나의 열을 놓는다.

 

그리고 이 열을 놓았을 때 문제가 없는지 (기존에 넣은 열들과 겹치는 부분이 없고 대각선으로도 공격받지 않는지)를 확인한다.

이미 행마다 하나의 열을 놓기 때문에 위 아래 공격을 받지 않는지는 확인할 필요가 없다.

 

그리고 놓고 나서는 백트래킹을 통해서 모든 경우의수를 본다.

 

check하는 함수는 아래 코드이다.

 

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

 

전체 코드 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int N, Answer;
int row[12];

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

void dfs(int rowNum){
    if (rowNum==N){
        Answer++;
        return;
    }
    for (int i=0;i<N;i++){
        row[rowNum] = i;
        if (check(rowNum)){
            dfs(rowNum+1);
        }
        row[rowNum] !=i;
    }
}

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