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

[문제]

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

9663번: N-Queen

[문제풀이]

유명한 백트래킹 응용문제 n 퀸인데 기존에 백트래킹을 많이 풀어봤다면 충분히 풀 수 있을만한 문제다.

체스판에서 N만큼 퀸이 존재하는 경우를 요구하는 문제인데 체스판에 퀸이 N만큼 존재할려면 모든 줄에 퀸이 1개씩은 존재해야 한다.

다만, 이미 방문했던 위치를 true나 false로 둘 경우 다시 원상복귀할때 원하지 않는 부분까지 반환을 해주는 경우가 생기기에 2중배열 visit을 int로 둔 뒤 N번째 퀸이 왔었는지를 더해주고 N번째 퀸이 빠질때 다시 N만큼을 빼는 방법으로 체크를 했다.

이런식으로 체크를 하게 된다면 1,2,3,4 퀸이 방문을 하고 4번퀸이 빠진다면 해당 위치는 6이 될 것이고 1이 다시 나간다면 5가 되는 식으로  되므로 0인지 아닌지만 체크를 해주면 된다.

 

퀸이 N개 만큼 있다면 answer를 1개 증가시킨다.(해당 코드에서는 처음 시작을 1로 정했기 때문에 N+1개만큼 일치한다면의 조건이다.)(83~86)

각 줄에 퀸은 1개밖에 존재하지 않으므로 for문을 1개만 돌려도 충분하다.(88)

만일 해당 위치에 이미 방문을 했다면 패스해주자.(89~91)

퀸이 갈 수 있는 모든 위치를 방문해주자(92)

퀸을 추가했다면 재귀를 통해 체스의 다음번째 줄로 가자(93)

방문이 끝났다면 갔던 모든 위치를 다시 원상복귀해주자(94)

 

해당 문제에서 쉽게 틀릴 수 있을 만한 부분 중 하나로 퀸의 방문 위치를 체크해 주는 부분이다.

4 X 4 의 배열에서 1,1 에 퀸이 간다면 대각선 좌측 상단방향으로는 1번만 가면 되지만 우측 하단 방향으로는 2번을 가야 한계점이 나오기 때문이다. 

그러니 n만큼을 모두 가게 한 뒤에 if문을 통해 체크를 해서 위치가 넘지 않는다면 모두 체크를 해주자.(14~27)

퀸은 룩의 성질또한 갖고 있기에 세로축과 가로축을 모두 위 아래로 가주자.(29~41)

방문체크를 해제하는 부분도 똑같이 해주자.(46~79)

 

[코드]

#include<iostream>
#include<vector>
#define endl "\n"
 
using namespace std;
 
int n;
int answer;
int visit[17][17];
 
void DFS(int x, int y, int count){
    visit[x][y] += count;
 
    for(int i = 0;i<n;i++){
        if(count+i-1<n){
            visit[count+i-1][y] += count;
        }
        if(count-i-1>0){
            visit[count-i-1][y] += count;
        }
        if(y+i<n){
            visit[count-1][y+i] += count;
        }
        if(y-i>0){
            visit[count-1][y-i] += count;
        }
    }
 
    for(int i = 1;i<n;i++){
        if(x-i>=0 and y-i>=0){
            visit[x-i][y-i] += count;
        }
        if(x-i>=0 and y+i<n){
            visit[x-i][y+i] += count;
        }
        if(x+i<n and y+i<n){
            visit[x+i][y+i] += count;
        }
        if(x+i <n and y-i>=0){
            visit[x+i][y-i] += count;
        }
    }
    return;
}
 
void dfsRelease(int x, int y, int count){
    visit[x][y] -= count;
 
    for(int i = 0;i<n;i++){
        if(count+i-1<n){
            visit[count+i-1][y] -= count;
        }
        if(count-i-1>0){
            visit[count-i-1][y] -= count;
        }
        if(y+i<n){
            visit[count-1][y+i] -= count;
        }
        if(y-i>0){
            visit[count-1][y-i] -= count;
        }
    }
 
    for(int i = 1;i<n;i++){
        if(x-i>=0 and y-i>=0){
            visit[x-i][y-i] -= count;
        }
        if(x-i>=0 and y+i<n){
            visit[x-i][y+i] -= count;
        }
        if(x+i<n and y+i<n){
            visit[x+i][y+i] -= count;
        }
        if(x+i <n and y-i>=0){
            visit[x+i][y-i] -= count;
        }
    }
    return;
}
 
void backtracking(int count){
 
    if(count == n+1){
        answer++;
        return;
    }
 
   for(int i = 0;i<n;i++){
        if(visit[count-1][i] != 0){
            continue;
        }
        DFS(count-1,i, count);
        backtracking(count+1);
        dfsRelease(count-1,i,count);
    }
 
    return;
}
 
int main(){
    cin>>n;
    backtracking(1);
    cout<<answer<<endl;
    return 0;
}