[백준] 9663번 N-Queen -C++

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

문제 요약 :

N X N 체스판에서 N개의 퀸을 서로 공격할 수 없게 위치시키는 경우의 수 찾기

🧀 N-Queens

N개의 Queen을 서로 상대방을 위협하지 않도록 NxN 판에 위치시키는 문제

• 서로 상대를 위협하지 않도록
  • 같은 행, 같은 열, 같은 대각선 상에 위치 시키지 않아야한다.
• 각 세대별로 1번 Queen 을 놓는 경우의 수 N개, 2번 Queen 을 놓는 경우의 수 N개, N번 Queen 을 놓는 경우의 수 N개로
• 총 N개의 자식들을 가지는 N개의 깊이의 상태공간트리를 가진다.
  • 모든 경우의 수는 N X N +1 개가 된다.
  • 불필요한 재귀호출을 수행하지 않도록 유망한 노드만 세는 게 합리적이다. → 백트래킹

깊이우선탐색 + 되추적 알고리즘을 사용하는게 적합하다.

풀이 방법

• 두 말을 같은 행, 같은 열, 같은 대각선에 둘 수 없다.
  • 열의 차이와 행의 차이가 같으면 대각선의 위치가 같은 셈이다.

if(col(i) == col(k)) //같은 열(행)에 위치시키는 경우 -> 유망하지 않다.

if(abs(col(i)-col(k)) == abs(i-k))//열의 차이와 행의 차이가 같다.
															//대각선 위치가 같다 -> 유망하지 않다.

• 0,0( 0번 행, 0번 열) 부터 시작해서 한 행씩, 한 열씩 유망성을 검사한다.
  • 0번 행에서 0번 열의 위치가 유망하다면 다음 행으로 이어서 진행한다.
    • 자식 노드로 이동하듯이 다음 행으로 쭉쭉 진행(DFS)
  • 해당 노드가 유망하지 않다면 현재 행의 다음 열 (0,1)로 이동한다.
• N번 행에 다다를 때까지 진행
  • N번 행에 도착하면 경우의 수를 증가시킨다.

풀이

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

int N;
vector<int> col;
int answer = 0;

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

void DFS(int row){
    if(row == N){
        answer++;
        return;
    }
    for(int column = 0; column < N; column++){
        col[row] = column;//0,0위치부터 퀸을 놓기 시작
        
        if(promising(row)){
            DFS(row + 1);//다음 행 진행
        }
        //유망하지 않다면 다음 열 진행
    }
}

int main(){
    cin >> N;
    col.resize(N);
    
    DFS(0);
    
    cout << answer <<endl;
    return 0;
}

주석 추가

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

int N;
vector<int> col;
int answer = 0;

//유망성 여부를 확인하는 함수
bool promising(int row){
		//현재 행에서 
    for(int i = 0; i < row; i++)
    {
				//같은 열에 위치되거나 대각선에 퀸이 놓여있으면 false
        if(col[i] == col[row] || abs(col[i] - col[row]) == abs(i - row)){
            return false;
        }
    }
    //그렇지 않으면 유망하다
    return true;      
}

//DFS로 체스판 위에서 말을 이동시킬 함수
void DFS(int row){
		//N번째 행까지 말을 위치시켰으면 경우의 수를 증가시킨다.
    if(row == N){
        answer++;
        return;
    }
	  //현재 행에서 열을 옮기면서 반복
    for(int column = 0; column < N; column++){
        col[row] = column;//0,0위치부터 퀸을 놓기 시작
        //현재 위치가 유망하다면
        if(promising(row)){
            DFS(row + 1);//다음 행 진행(깊이 우선 탐색)
        }
        //유망하지 않다면 현재 행의 다음 열 진행(가지치기)
    }
}

int main(){
    cin >> N;
    col.resize(N);//벡터 크기 설정
    
    DFS(0);//0번 행부터 시작
    
    cout << answer <<endl;
    return 0;
}