[백준/C++] 9663 : N-Queen

https://www.acmicpc.net/problem/9663

문제

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

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

 

입력

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

출력

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

---

main ideas

1. 어차피 matrix로 두어도 같은 행과 열에는 퀸을 못 두므로 이차원배열이 아니라 일차원 배열로 풀 수 있다. 

 

2. 퀸이 있는 곳과 같은 행, 같은 열, 대각선에는 다른 퀸을 놓지 못한다.

따라서 일차원 배열의 i 번째 열에 퀸을 놓고, 열이 겹치거나 대각선에 있다면 중지한다. (backtracking)

이때, 대각선 확인은 (x,y) (x+1,y+1) 이 대각선(기울기가 1)임을 이용한다. (x끼리의 차 == y끼리의 차)

 

3. canGo() 에서 true가 반환되면, 그 다음 행으로 이동한다.

놓은 퀸의 갯수가 n개가 되면 answer을 1만큼 증가시킨다.

 

나의 풀이

#include <iostream>
using namespace std;

int n;
int line[15] = {0};
int answer = 0;

bool canGo(int x){
    for (int i = 0; i < x; ++i){
        if(line[x] == line[i]) return false; // y값이 같다?(같은 열이다?) false
        if(abs(line[x]-line[i]) == x-i) return false; // 대각선 라인이다? false
    }
    return true;
}

void queen(int x){
    if(x==n) {
        answer++;
    }
    else{
        for (int i = 0; i < n; ++i){
            line[x] = i; // x행의 i번째 열에 퀸 놓기
            if(canGo(x)) queen(x + 1);
        }
    }
}

int main(){
    cin >> n;
    queen(0);
    cout << answer;
    return 0;
}