[프로그래머스 Level 2, C++] N-Queen

문제 : N-Queen

---

풀이 방법

솔직히 잘 모르겠다

 

문제의 질문하기에서 2차원으로 하지말고 1차원으로 해야 효율성에서 통과할 수 있다고 하고

기존 체스와 새로운 체스의 각행과 열의 차의 절대값이 같으면 기울기가 같으니

대각선 체크를 할 수 있다고 하는데 도통 뭔소린지 모르겠더라

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

https://cryptosalamander.tistory.com/58

[백준 / BOJ] - 9663번 N-Queen C++ 풀이

그래서 그냥 다른사람 푼거 코드를 보면서 이해나 하려고 보면서 풀었다

이 사람꺼 보고 했는데 아래 영상 보고 코드를 다시 보니까 어떻게 돌아가는지는 알겠는데

엄청 어렵네;;;

 

 

---

소스 코드

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

void dfs(vector<int>& chess, int& answer, int col) {
    if(chess.size() == col) {
        answer++;
    }
    else {
        for(int i=0; i<chess.size(); i++) {
            bool flag = true;
            chess[col] = i;
            
            for(int u=0; u<col; u++) {
                if(chess[col] == chess[u] || abs(chess[col] - chess[u]) == abs(col - u)) {
                    flag = false;
                    break;
                }
            }
            if(flag) dfs(chess, answer, col+1);
        }
    }
}

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