알고리즘
[C++] Boj 9663 N-Queen
(ꐦ •᷄ࡇ•᷅)
2025. 1. 16. 09:55
문제 링크
접근
역시 백트래킹 연습 문제이다. 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제인데, 중요한 건 나는 체스의 룰을 모른다. 그래서 퀸의 이동 규칙을 찾아봤다.
퀸의 이동 규칙
- 퀸은 상하좌우 맨 끝까지 이동할 수 있다.
- 퀸은 4방향 대각선 맨 끝까지 이동할 수 있다.
문제 적용
N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이므로, 일단 같은 행에는 1개의 퀸만이 위치할 수 있다는 걸 알 수 있다. 이렇게 규칙을 찾아보면,
- 퀸은 다른 퀸과 같은 행에 있을 수 없다.
- 퀸은 다른 퀸과 같은 열에 있을 수 없다.
- 좌측 하단과 우측 상단을 연결하는 대각선이 있고 (x, y)에 퀸이 있을 때 x + y의 값이 n이라고 하자.
- 그렇다면 다른 퀸은 x' + y' = n인 좌표에 있을 수 없다.
- 같은 대각선이라는 뜻이므로.
- 마찬가지로 좌측 상단과 우측 하단을 연결하는 대각선이 있고 (x, y)에 퀸이 있을 때 x - y의 값이 n이라고 하자.
- 그렇다면 다른 퀸은 x' - y' = n인 좌표에 있을 수 없다.
이제 이 좌표를 isUsed 표시를 해서 백트래킹을 해 주면 된다!
코드
#include<iostream>
using namespace std;
// 같은 열인지 확인
bool isUsed0[30];
// 같은 ↗ 대각선 상에 있는지 확인
bool isUsed1[30];
// 같은 ↘ 대각선 상에 있는지 확인
bool isUsed2[30];
// 1 <= n < 15
int n;
int cnt;
// curX번째 행마다 퀸을 하나씩 배치 예정
void Solve(int curX)
{
if (curX == n)
{
cnt++;
return;
}
// (curX, i)에 퀸을 놓는다.
for (int i = 0; i < n; i++)
{
// curX - i + n - 1 는 index out of range 방지
if (isUsed0[i] || isUsed1[curX + i] || isUsed2[curX - i + n - 1]) continue;
isUsed0[i] = true;
isUsed1[curX + i] = true;
isUsed2[curX - i + n - 1] = true;
Solve(curX + 1);
isUsed0[i] = false;
isUsed1[curX + i] = false;
isUsed2[curX - i + n - 1] = false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
Solve(0);
cout << cnt;
return 0;
}