[백준 #9663] N-Queen

개요

---

백트래킹.

가지치기를 이용한다. dfs를 끝까지 갈 필요 없이 중간 가지를 자르면 된다.

board라는 2차원 벡터에다 퀸을 놓을 수 있는지 여부를 저장한다.

퀸을 자리를 바꿔가면서 놔야하는데, 그때마다 [놓고 -> 다음 dfs돌고 -> 놓은거 다시 빼고] 과정을 거쳐야 함. 

이 때 이전 상태를 복구하는 과정(빼는 과정)때 bool로 true/false힘들게 할 필요 ㄴㄴ

그냥 상태 변화시킬때 +=1(놓기), -=1(빼기) 해주기. 종만북 boardcover했던거처럼.

 

그리고 어차피 계속 행은 아래로 증가시키기때문에

상태를 변화시킬때 같은행~그 이전행들은 신경쓸 필요가 없다.

 

나는 퀸이 영향을 주는 자리를 기준으로 코드를 짰는데

다른 사람들은 퀸의 위치를 기준으로 코드를 짰다.

board[][]대신 queen[]이라는 배열에 퀸의 위치(j)를 저장해두고 짰더라. 그럴수도 있구나.

 

 

코드 (정답, 1984KB, 1440ms)

---

/**
 * @name: N-Queen
 * @link: https://www.acmicpc.net/problem/9663
 * @date 2020-05-04
 * @author sunmon
 * TIP: 
**/
#include <iostream>
#include <vector>
using namespace std;


vector<vector<int> > board; //board[i][j] : 해당 칸을 공격할 수 있는 퀸의 개수

//board[i][j]에 영향을 주거나 취소한다
void cover(int i, int j, int n, int flag){
    for(int k = 1; k < n-i; ++k){
        board[i+k][j] += flag;  //같은열
        if(j+k<n) board[i+k][j+k] += flag;  //대각선오른쪽아래
        if(j-k>=0) board[i+k][j-k] += flag; //대각선왼쪽아래
    }
}

int solve(int n, int i){
    if(i == n) return 1;
    int ret = 0;
    for(int j = 0; j<n; j++){
        if(board[i][j]) continue;
        cover(i,j,n,1); //못 놓는 곳 체크
        ret += solve(n, i+1);
        cover(i,j,n,-1); //못 놓는 곳 체크해제
    }
    return ret;
}


int main(){
    int n;
    cin >> n;
    board = vector<vector<int> >(n, vector<int>(n, 0));
    cout << solve(n, 0);
}

 

 

결과

---

빨라용(디버깅모드로 빌드해서 좀 느리게 나왔다)