백준 - 9663 N-Queen

N-Queen

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

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

✔ 접근방법

DFS, 백트래킹

1. 재귀호출를 이용한 DFS 구현
2. 탈출조건 정의
3. 유망 조건 정의

✔ 코드

#include <stdio.h>
#include <vector>
#include <stdlib.h>

using namespace std; 

int n;
int cnt;
vector<int> v_col; // 놓여진 Q를 저장, v_col[row-1]로 row에 놓여진 Q의 col 리턴

bool promising(int row, int col){
    for( int v_row=0; v_row<v_col.size(); v_row++ ){
        /* 같은 열 또는 대각선 위에 있는 지 확인 */
        if(v_col[v_row] == col || abs(v_col[v_row]-col) == abs((v_row+1)-row)){
            return false;
        }
    }
    return true;
}

/* row에서 가능한 Q의 col을 찾는 함수 */
void nqueen(int row){
    if( row > n ){
        cnt++;
        return ;
    }
    
    for(int col=1; col<=n; col++){
        if(promising(row, col)){
            v_col.push_back(col);
            nqueen(row+1);
            v_col.pop_back();
        }
    }
    return ;
}

int main(void){

    scanf("%d", &n);

    nqueen(1);

    printf("%d\n", cnt);

    return 0;
}

☝ 팁

• 서로 다른 두개의 퀸은 같은 열과 대각선에 위치하면 안된다. 이를 판단하기 위한 조건식은 아래와 같다.

  Promising function
  두개의 Queen이 같은 열 또는 대각선에 있는지 확인해야 한다.
  - col(i) : Queen이 i번째 행에 있는 열 번호
  if ( col(i) == col(k) ) => nonpromising;
  - k번째 행의 여왕이 같은 대각선에 있는지 확인하는 방법은 무엇일까?
  if(abs(col(i) - col(k)) == abs(i-k)) => nonpromising;

👍 참고 사이트

백준 9663 문제