[백준 9663번] [백트레킹] N-Queen

접근 자체는 잘했는데, 중복해서 셀 수 있는 것을 놓쳐서 많이 헤맸다.

 

종만북 6.5장처럼 이러한 배열 문제에서 중복을 피할 수 있는 가장 쉬운 방법은

조건을 만족하는 것 중 가장 왼쪽 상단을 잡는 방향으로 진행하는 것이다.

(이 지점을 놓친 것에 대해서 매우 반성하도록 하자.)

 

일단 문제 접근 방법은 다음과 같다.

1. 퀸의 공격 방향은 상하좌우대각이다.

2. 행, 열, 대각 성분을 따로 DP형태로 저장해놓는다.
퀸의 공격 성질을 감안해보면 각 행, 열, 대각 성분에 1개씩만 들어갈 수 있다는 것과 동치이기 떄문이다.

3, 반복적으로 비어있는 최초의 행을 찾고 그것을 기준으로 어떠한 열에 넣을 수 있는지를 기준으로 분할하여 계산한다.
(실질적으로 함수 내부에서 N^2이라고 생각하기 쉬우나 실질적으로는 N이라서 시간 초과에 걸리지 않는다.)

해당하는 내용으로 코드를 구현한 결과는 다음과 같다.

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

using namespace std;
typedef long long ll;

int up_down[16];
int right_left[16];
int cross_first[32];
int cross_second[32];
int N;
ll result = 0;

void backtrack(int check_num){
    if(check_num == N){
        result += 1;
        return;
    }
    else{
        for(int i = 0; i < N; i++){
            if(right_left[i] == 1) continue; // Already visit
            bool available_check = false;
            for(int j = 0; j < N; j++){
                if(up_down[j] == 1) ;
                else{
                    if(cross_first[i + j] == 0 && cross_second[i - j + (N - 1)] == 0){
                        right_left[i] = 1;
                        up_down[j] = 1;
                        cross_first[i + j] = 1;
                        cross_second[i - j + (N - 1)] = 1;
                        backtrack(check_num + 1);
                        right_left[i] = 0;
                        up_down[j] = 0;
                        cross_first[i + j] = 0;
                        cross_second[i - j + (N - 1)] = 0;
                        available_check = true;
                    }
                }
            }
            break;
        }
        return;
    }
}

int main(void){
    cin >> N;

    backtrack(0);

    cout << result << "\n";
    return 0;
    
}

잘 복습하도록 하자.