문제 링크
접근한 방식
백트래킹으로 접근하였다. 백트래킹이란, 탐색을 수행하다가 유망하지 않은 노드의 경로로는 더이상 탐색하지 않고 다시 부모 노드로 돌아가 다른 길로 탐색하는 기법이다.
백트래킹은 불필요한 탐색을 수행하지 않게하여 시간을 절약할 수 있게 해준다.
우선 체스에서의 퀸 이동 가능 범위를 알아보자.
퀸은 자신이 있는 위치를 기준으로하여 동서남북 또는 대각선에 위치하는 지점은 어디든 이동할 수 있다.
예를 들어 다음 사진과 같이 제일 왼쪽 위 위치에 퀸이 하나 있다면 다른 하나의 퀸은 X에는 위치할 수 없고, O에만 위치할 수 있게 된다.
문제에서는 N X N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하라고 하였다.
그런데 퀸의 이동범위에 의하여 하나의 가로줄에는 2개의 퀸이 위치할 수 없기 때문에, 퀸 N개를 배치하기 위해서는
1. 하나의 가로줄에 1개의 퀸이 위치하면서
2. 모든 가로줄에 대해 적어도 1개의 퀸이 위치해야 한다.
따라서 DFS로 체스판을 탐색하면서, 퀸을 놓을 수 없는 위치는 그 경로를 더이상 탐색하지 않고 같은 행에 있는 다른 위치로 가서 탐색을 수행하면 된다.
이때, 퀸을 놓을 수 있는 위치인지 판별하기 위해서 이미 존재하는 퀸들로부터 공격당할 수 있는지 아닌지를 판별해야 한다. 필자는 다음과 같이 판별하였다.
이미 존재하는 퀸 위치 = (row1, col1), 판별할 위치 = (row2, col2) 라고 할때
1. (row1 == row2) 이면 공격당함
2. (col1 == col2) 이면 공격당함
3. ((row1 - row2)의 절대값 == (col1 - col2)의 절대값) 이면 공격당함
4. 1, 2, 3 중 해당 사항 없다면 공격당하지 않음
그리고 마지막 행까지 도달하였을때는 탐색에 성공한것으로 처리한다.
탐색 구조를 그림으로 나타낸다면 다음과 같다.
1행 1열에 퀸을 위치시키는 것으로 시작하여 탐색을 시작하고, 탐색 위치가 공격당할 수 있는 위치면 더이상 탐색하지 않는 것을 그림으로 나타낸 것이다.
코드
C++
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int N;
int result;
vector<pair<int, int>> queenExistLocation; // 이미 퀸이 존재하는 위치에 대한 배열
// 이미 존재하는 퀸으로부터 공격당하지 않는지 판별하는 메소드
bool canPutQueen(const int& row, const int& col) {
for (pair<int, int> p : queenExistLocation) {
int i = p.first;
int j = p.second;
// 같은 행 또는 같은 열 또는 대각선에 퀸이 이미 존재하면 false
if (row == i || col == j || fabs(row - i) == fabs(col - j))
return false;
}
return true;
}
void dfs(const int& row) {
// 마지막 행까지 탐색이 되었다는 것은 조건을 만족하는 경우임
if (N == row) {
result++;
return;
}
for (int j = 1; j <= N; j++) {
// 다음 행 중에서 퀸을 배치할 수 있는 위치로만 DFS
if (canPutQueen(row + 1, j)) {
queenExistLocation.push_back(make_pair(row + 1, j));
dfs(row + 1);
queenExistLocation.erase(queenExistLocation.end() - 1);
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
dfs(0);
cout << result << '\n';
return 0;
}