[Baekjoon] 9663번 N-Queen문제.cpp

[백준] 9663번 N-Queen 문제 링크

여러 차례의 시도 끝에 유의미한 정도로 실행 시간을 줄였다.

· 기본 아이디어

N-Queen 문제는 N*N 맵에 N개의 퀸이 서로 공격할 수 없게 놓는 문제이다. 퀸은 상하좌우대각으로 거리제한 없이 이동할 수 있기 때문에 선상에 다른 퀸이 놓이는 경우를 배제하는 식으로 백트래킹을 작성한다.

· 아이디어의 변천사

#1

기본적으로 가로줄에 영향을 받지 않도록 가로줄 번호에 따라 재귀적 호출을 하도록 설정했다. 그리고 세로줄과 대각에 대한 처리를 해줘야 하는데, 배열에서 같은 대각선에 위치하는 값들의 특징은 다음과 같다.

• / 방향의 대각선 : 좌표 x + y의 값이 같다.
• \ 방향의 대각선 : 좌표 x - y 또는 y - x의 값이 같다.

따라서 열, / 대각, \ 대각에 대한 벡터를 만들고 퀸을 놓을 수 있는 칸에서의 x(열), x + y, x - y 값을 원소로 추가해주었다. 그리고 새로운 칸에 도달할 때마다 각 선상에 대한 값을 계산해주고 벡터에 같은 값이 존재하는지 비교해주었다.

하지만 매 칸마다 어떤 선상에 위치하는지에 대한 계산이 필요했고, 선마다 반복문 및 중복 체크를 위한 if문을 삽입한 탓에 굉장히 시간이 오래 걸렸다.

#2

반복문의 수를 줄이기 위해 열 값을 저장하는 벡터만 두고 나머지를 삭제하였다. col[x] = y와 같이 x를 인덱스로 벡터에 접근하면 퀸이 놓인 y 값을 얻을 수 있다. 이를 이용해 한 번의 반복문 안에서 / 대각의 값과 \ 대각의 값을 매번 연산해주었다.

물론 연산량이 많은 탓에 크게 실행 시간이 단축되진 않았다.

#3

연산이 많은 것이 문제이다. 따라서 연산 자체를 줄여야 한다. / 대각도 서로다른 대각이라면 다른 x + y 값을 갖는다. 따라서 각 선이 존재할 수 있는 최대 범위까지 배열을 만들고 해당 선상에 놓을 수 있는지 없는지만 판단하면 된다.

말이 조금 어려운데, 예를 들어 {0, 0}이 지나는 / 대각의 x + y 값은 0이고, {0, 1}이 지나는 / 대각의 x + y 값은 1이다. 일치하지 않는 선이라면 서로 다른 값을 가지므로 특정 선상에 퀸이 존재하는지 여부를 bool 값으로 저장하였다.

그리고 특정 지점에 퀸을 놓으려 할 때 좌표의 계산을 수 차례 거칠 필요 없이 바로 참거짓을 판단할 수 있다.

최종적인 알고리즘을 적용한 소스 코드는 아래와 같다.

#include <iostream>
#include <vector>

int n;
int queenCnt = 0;
int caseCnt = 0;
bool overlapped;
bool col[32];
bool rightDiagonal[32];
bool leftDiagonal[32];

void back_tracking(int line){
    if(queenCnt == n){
        caseCnt++;
    }
    else{
        for(int index = 1; index <= n; index++){
            if(!col[index] && !leftDiagonal[index + line] && !rightDiagonal[index - line]){
                col[index] = true;
                leftDiagonal[index + line] = true;
                rightDiagonal[index - line] = true;
                queenCnt++;

                back_tracking(line + 1);

                col[index] = false;
                leftDiagonal[index + line] = false;
                rightDiagonal[index - line] = false;
                queenCnt--;
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::cin >> n;

    back_tracking(1);
    std::cout << caseCnt << '\n';
}