[프로그래머스] N-Queen

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int DFS(int row, int n, vector<int> &cols) {
    if (row == n) {
        return 1;
    }
    
    int ways = 0;
    
    for (int col = 1; col <= n; col++) {
        bool isValid = true;
        
        for (int prevRow = 0; prevRow < row; prevRow++) {
            if (cols[prevRow] == col || abs(cols[prevRow] - col) == abs(prevRow - row)) {
                isValid = false;
                break;
            }
        }
        
        if (isValid) {
            cols[row] = col;
            ways += DFS(row + 1, n, cols);
        }
    }
    
    return ways;
}

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

---

📝 풀이

cols에 각 행에 퀸의 열 위치를 저장합니다.

DFS 재귀 함수를 수행합니다.

모든 행에 퀸을 배치한 경우는 1을 return 합니다.

같은 열에 있거나 대각선에 위치하는 경우를 제외하고 가능한 행에 퀸을 배치합니다. 

퀸을 배치할 때 다음 행으로 이동하여 재귀적으로 퀸을 배치합니다.

최종적으로 계산된 answer을 return 합니다.