백준 9663 N-Queen | 백트래킹, DFS | C++

 

 

이번 포스팅은 백준 9663번 N-Queen입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

 

기본 알고리즘

DFS, 백트래킹

 

풀이는 주석에 담았습니다.

 

 

 

전체 코드

 

//백준9663 N-Queen
#include <iostream>
using namespace std;
 
const int MAX = 15 + 1;
int N;
int map[MAX] = { 0, }; //map[a]=b는 a행 b열에 queen 배치함을 의미            
int ans = 0; //출력
 
//유망한가
bool isPromsing(int row) { 
    //i번째 행에 queen을 놓을때 
    //0~(row-1)행에 이미 놓인 queen과 문제를 일으키는지 검사
    for (int i = 0; i < row; i++) {
        //같은 열에 queen이 이미 있으면 배치할 수 없다
        if (map[row] == map[i])
            return false;
        //대각선에 queen이 이미 있으면 배치할 수 없다
        //행의 index 차이와 열의 index 차이가 같으면 대각선 위치
        else if (abs(map[row] - map[i]) == abs(row - i))
            return false;
    }
 
    return true;
}
 
//배치
void nQueen(int row) { 
    if (row == N) {
        /*for (int i = 0; i < N; i++) {
            cout << map[i] << " ";
        }
        cout << "\n";*/
        ans++;
    }
    //row행에 queen을 배치
    else {
        for (int i = 0; i < N; i++) {
            map[row] = i; //row행 i열에 queen을 놓았다.
            if (isPromsing(row)) { //i열에 배치가 유망하면(가능하면)
                nQueen(row + 1); //다음 행으로
            }
        }
    }
}
 
int main() {
    cin >> N;
 
    nQueen(0); //0행부터 배치 시작
    cout << ans;
 
    return 0;
}