백준(BOJ) 그래프순회(백트랙킹) N-Queen (9663) - Gold 4

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

 

문제 해결

백트랙킹의 전형적인 문제중 하나인 N-Queen 문제이다. N-Queen이 겹치지 않으려면 현재 Queen의 위치에서 가로축, 세로축 그리고 X자 대각선 모두 겹쳐서는 안된다. 이 경우 Queen이 움직일 수 있는 체스판의 위치를 하나의 노드로 생각하여 상태공간트리를 만들어 DFS 그래프 탐색을 하면 된다. 이 때 백트랙킹의 경우 DFS탐색 중 더 이상 가능성이 없는 노드는 탐색하지 않는다. 이 문제에서 중요한 포인트는 2가지이다. Queen의 이동경로를 체크하여 이동 가능성 확인, 현재 체스판의 Queen이 어디에 위치했는지 확인. 이 2가지를 중요 포인트로 문제를 풀면 된다. 

1. Queen이 체스판에 어디에 위치해 있는지 확인하기 위해서는 직관적으로 N x N의 2차원 배열 체스판을 만들어도 되지만 간단하게 1차원 배열로도 확인이 가능하다.

- N = 4인 경우 4칸짜리 배열을 만들고 인덱스를 Y축, 인덱스안에 들어있는 값을 X축으로 생각하여 접근할 수 있다. 

ex) [1] [3] [0] [2]

위와 같은 경우  [0,1], [1, 3], [2, 0], [3, 2] 위치에 퀸이 있다고 볼 수 있다.

 

2. 위 체스판 배열을 이용하여 Queen을 놓을 수 있는지 여부 확인

- 가로 중복 확인 : 인덱스를 하나씩 증가하면서 지나가므로 1차원 배열의 경우 가로축으로 겹칠 가능성은 없다.

- 세로 중복 확인 : 현재까지 지나온 인덱스를 하나씩 확인하면서 안에 들어 있는 값이 현재 넣으려는 값과 같다면 세로축이 겹친다는 의미

ex) [1] [3] 까지의 경우 다음 index인 2번 index에서 [1]이 온다면 -> [1] [3] [1]와 같은 배열이 만들어지고 이 때 2번 인덱스를 제외한 0번 인덱스와 1번 인덱스의 값을 확인하여 중복된 값이 있는경우 세로축으로 Queen의 중복이 발생했다는 의미이다.

- X 대각선 중복 확인 : 이 부분이 조금 까다로울 수 있는데 이 부분은 간단한 식으로 해결이 가능하다.  

ex) [1] [3] 까지의 경우 다음 index인 2번 index에서 [2]가 온다면 대각선으로 겹치는 경우이며 [1] [3] [2]와 같은 배열이 만들어지고 이 때 현재 index + 넣고자 하는 값 == 0번 인덱스와 그 값, 1번 인덱스와 그 값이 같은게 하나라도 있다면 대각선으로 중복이다.

마찬가지로 index - 넣고자 하는값 == 0번 인덱스 - 0번 인덱스 값 or 1번 인덱스 - 1번 인덱스 값중 같은 값이 하나라도 있다면 대각선 중복이된다.

 

위 2가지 점을 기준으로 0번 인덱스부터 N-1번 인덱스까지 순회를 하면서 N-Queen의 가능성을 재귀적으로 탐색하면 쉽게 문제를 해결할 수 있다.

 

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
ll answer;

bool isPromise(vector<ll> &visit, ll index, ll i){
    for(ll j = index-1; j>=0; j--){
        if(visit[j] == i)
            return false;
    }
    for(ll j = index-1; j>=0; j--){
        if((index + i) == (j + visit[j]) || ((index - i))==((j - visit[j])))
            return false;
    }   
    return true;
}

void NQueen(vector<ll> &visit, ll index)
{
    if(index == visit.size()){
        answer = answer + 1;
        return;
    }
    
    for(ll i = 0; i<visit.size(); i++){
        if(isPromise(visit, index, i) == true){
            visit[index] = i;
            NQueen(visit, index+1);
            visit[index] = -1;
        }
    }
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt" , "r" ,stdin);

    ll N = 0;
    cin >> N;
    answer = 0;
    vector<ll>visit(N, -1);
    for(ll i=0; i<N; i++){
        visit[0] = i;
        NQueen(visit, 1);
        visit[0] = -1;
    }
    cout << answer << "\n";
    return 0;
}

문제 풀이는 어렵지 않은데 막상 구현하려니 생각보다 빡 이해가 되지는 않는 문제인것 같다...