백준 문제 링크 : 9663번: N-Queen (acmicpc.net)
백준 9663번 N-Queen 문제 사진
문제 요약
입력 값 : N(체스판의 세로 및 가로 길이)
- 각각의 여왕은 서로 공격할 수 없어야 한다
- 위 조건을 만족하는 경우의 갯수를 출력하라
문제 풀이 과정
이 문제를 한 줄로 요약하자면 입력된 가로,세로 길이를 가지는 체스판에 배치되는 여왕들이 서로 공격할 수 없도록 여왕 말을 배치할 수 있는 모든 경우의 수의 갯수를 출력하라 라고 할 수 있을 것 같습니다.
제 지식 한도 내에서 이 문제를 풀 수 있는 방법이 두 가지가 있다고 생각했어요.
첫번째 방법은 각각의 여왕을 배치하는 동시에 해당 여왕의 공격 경로를 체스판에 표시를 해두고 표시된 위치에는 이후 여왕을 배치할 수 없도록 구성하는 방법입니다.
두번째 방법은 체스판에 표시를 하는 것이 아니라 각각의 여왕의 위치를 저장해두고 새로운 여왕을 배치할 때 아래 조건에 따라 공격 가능 여부를 확인하는 방법입니다.(각각의 여왕을 a와 b라고 칭하겠습니다.)
- a와 b의 x축 y축 좌표가 하나만 동일해도 서로 공격할 수 있다.(직선 공격 범위)
- a와 b의 각각의 좌표를 뺀 절댓값이 동일할 경우 서로 공격할 수 있다.(대각선 공격 범위)
제한 시간이 10초인 문제이고 백트래킹을 사용하는 만큼 시간이 여유롭지 않아서 데이터를 캐싱해서 연산을 조금 더 줄일 수 있는 첫번째 방법을 먼저 구현해봤습니다.
#include <iostream>
#include <vector>
using namespace std;
int n;
int result_count = 0;
pair<int,int> direction[8] ={
{0,1},
{1,1},
{1,0},
{1,-1},
{0,-1},
{-1,-1},
{-1,0},
{-1,1},
};
int chess_map[16][16] = {0};
void fill_queen(pair<int,int> pos,int num){
chess_map[pos.first][pos.second] += num;
for (int i = 0; i < 8; i++) {
int curX = pos.first + direction[i].first;
int curY = pos.second + direction[i].second;
while (curX >= 0&&curX<n&&curY >= 0&&curY <n) {
chess_map[curX][curY] += num;
curX += direction[i].first;
curY += direction[i].second;
}
}
}
void backtracking(int layer)
{
if (layer == n) {
result_count++;
}
else {
for (int i = 0;i < n;i++) {
pair<int,int> pos(i,layer);
if (chess_map[pos.first][pos.second] > 0) continue;
fill_queen(pos, 1);
backtracking(layer+1);
fill_queen(pos, -1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
backtracking(0);
cout << result_count << endl;
return 0;
}실행 시간은 5초 가량 걸렸습니다. 이후 두번째 방법으로도 구현하여 테스트 해보았습니다.
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int n;
int result_count = 0;
vector<pair<int,int>> queens;
int chess_map[16][16] = {0};
bool is_attackable(pair<int,int> a,pair<int,int> b)
{
if (a.first == b.first) {
return true;
}
if (a.second == b.second) {
return true;
}
if (abs(a.first - b.first) == abs(a.second - b.second)) {
return true;
}
return false;
}
bool is_all_not_attakable(pair<int,int> pos)
{
for (int i = 0; i < queens.size();i++) {
if (is_attackable(queens[i],pos)) {
return false;
}
}
return true;
}
void backtracking(int layer)
{
if (layer == n) {
result_count++;
}
else {
for (int i = 0;i < n;i++) {
pair<int,int> pos(i,layer);
if (is_all_not_attakable(pos)) {
queens.push_back(pos);
backtracking(layer+1);
queens.pop_back();
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
backtracking(0);
cout << result_count << endl;
return 0;
}실행 시간은 약 7초 가량 나왔습니다. 새로운 배치를 할 때마다 캐싱된 값을 확인하는 것이 아니라 겹치는지 계산을 해야 했기 때문에 조금 더 느리게 나온 것 값습니다.
백트래킹 알고리즘을 사용한 다른 문제의 경우 아래 카테고리에서 찾아보실 수 있습니다.