[Baekjoon] 9663번 N-Queen문제.cpp
여러 차례의 시도 끝에 유의미한 정도로 실행 시간을 줄였다.
· 기본 아이디어
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';
}
Author And Source
이 문제에 관하여([Baekjoon] 9663번 N-Queen문제.cpp), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cedongne/Baekjoon-9663번-N-Queen문제.cpp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)