9663번-N-Queen

중요 지식

---

백트래킹 - 퀸이 놓여질 수 있는 모든 경우의 수를 탐색하기 위함

코드

---

#include <iostream>

using namespace std;

int N;
int queen_loc[15], count= 0;

int possible_loc(int row){
    for(int i = 0; i < row; i++){
        if(queen_loc[row] == queen_loc[i] || (row-i == abs(queen_loc[row] - queen_loc[i])))
            return 0;
    }

    return 1;
}

void NQueen(int row){
    if(row == N){
        count++;
        return;
    }

    for(int col = 0 ; col < N; col++){

        queen_loc[row] = col;

        if(possible_loc(row)){
            NQueen(row+1);
        }
    }

    return;
}

int main(){
    cin >> N;

    NQueen(0);

    cout << count;
  
    return 0;
}

풀이

---

알아둬야할 점

queen_loc[]의 의미:

queen_loc[a] = b : a행 b열에 퀸이 배치해 있다는 뜻이다

퀸이 놓여질 수 있는 자리인지 검사하는 방법

if(queen_loc[row] == queen_loc[i] || (row-i == abs(queen_loc[row] - queen_loc[i]))) { //code }

queen_loc[row] == queen_loc[i] : 퀸끼리 직성상에 있는지 확인

queen_loc[]의 특성상 행이 겹쳐지는 경우는 없으므로 열이 겹쳐지는 것만 확인하면 된다

row-i == abs(queen_loc[row] - queen_loc[i]) : 퀸끼리 대각선상에 있는지 확인

대각선의 있는 경우는 다른 퀸과의 행과 열의 거리가 같은 경우이다 

 

 

아래 더보기는 문제를 보고 작성하다만 부끄러운 코드이다

map[][]을 활용해서 퀸이 놓여질 수 없는 자리를 일일이 체크했다

#include <iostream>
#include <queue>

using namespace std;

int N, count = 0;
int map[15][15] = {0};

void func(int k){
    if(k == N){
        count++;
        return;
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(!map[i][j]){
                for(int x=0, y=j; x < N; x++) map[x][y]++;
                for(int x=i, y=0; y < N; y++) map[x][y]++;
                for(int x=i, y=j; x < N && y < N; x++, y++) map[x][y]++;
                for(int x=i, y=j; x >= 0 && y < N; x--, y++) map[x][y]++;
                for(int x=i, y=j; x < N && y >= 0; x++, y--) map[x][y]++;
                for(int x=i, y=j; x >= 0 && y >= 0; x--, y--) map[x][y]++;
                func(k+1);
                for(int x=0, y=j; x < N; x++) map[x][y]--;
                for(int x=i, y=0; y < N; y++) map[x][y]--;
                for(int x=i, y=j; x < N && y < N; x++, y++) map[x][y]--;
                for(int x=i, y=j; x >= 0 && y < N; x--, y++) map[x][y]--;
                for(int x=i, y=j; x < N && y >= 0; x++, y--) map[x][y]--;
                for(int x=i, y=j; x >= 0 && y >= 0; x--, y--) map[x][y]--;
            }
        }
    }

    return;
}

int main(){
    cin >> N;

    func(0);

    cout << count;
  
    return 0;
}