백트래킹 - 9663 N-Queen문제
N-Queen 문제는 백트래킹의 가장 대표적인 예제로서, 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다.
→ 이 문제를 풀기 위해서 N x N 배열을 만들 필요없고, 크기가 N인 일차원 배열을 만든 후, 각 열에 몇번째 행의 퀸이 있는지를 저장하면 된다.
ex) N = 4 일때,
일차원 배열 col[]에 저장
col[0] → 0번째 열에 존재하는 건 1행의 퀸이므로 1 저장, col[0] = 1
col[1] → 1번째 열에 존재하는 건 3행의 퀸이므로 3 저장, col[1] = 3
col[2] → 2번째 열에 존재하는 건 0행의 퀸이므로 0 저장, col[2] = 0
col[3] → 3번째 열에 존재하는 건 2행의 퀸이므로 2 저장, col[3] = 0
그 후, 한 행씩 퀸을 배치해가면서 총 배치 행수가 N이 되면 조건을 만족하는 경우의 수를 1개씩 늘려주는 방식으로 백트래킹을 진행할 수 있다.
→ 재귀함수의 매개변수에는 현재 몇 번째 행을 채우고 있는지를 기록하는 level이라는 인자를 사용해야한다
먼저 체크해야 하는 것
•
임의로 배치한 퀸이 다른 퀸과 같은 행 또는 같은 열에 있는가를 체크, 대각선에 위치해 있는가를 체크
→ 같은 행과 같은 열에 있는지 체크하는 방법은 매우 간단하지만, 대각선에 위치해 있는지를 찾는 방식이 다소 까다로울 수 있다.
→ 먼저 기본적으로 대각선에 존재하는 좌표일 경우, (X, Y)의 대각선에 위치한 좌표 (A, B)에서 반드시 X - A = Y - B를 만족한다.
→ 예를들어 (0, 1)을 기준으로 했을 때, 대각선에 있는 점들 (1, 2), (2, 3)은 반드시 (0 - 1) = (1 - 2) = -1, (0 - 2) = (1 - 3) = -2를 만족해야 한다는 것이다.
따라서, 우리가 정의한 col이라는 1차원 배열의 정의에 따라서, X좌표와 Y좌표의 차이가 일정한 값을 가질 경우, 해당 퀸과 대각선에 있다고 판단할 수 있다.
풀이 방향
1.
퀸은 서로 다른 행과 열에 위치해야하므로, 행이나 열 중 하나를 기준으로 잡는다
2.
크기 N인 배열을 선언하고, 이 배열의 0번 인덱스 값은 0행에서 위치한 퀸의 열번호를 의미한다
3.
1행에서 퀸이 위치해야 할 열을 정하고, 2행에서 퀸이 위치해야 할 열을 정한다
4.
성공적으로 N행까지 퀸을 위치시켰다면, 카운트를 진행한다
5.
퀸을 위치시킬 때, 퀸의 특성을 고려해준다
6.
퀸을 위치시키고자 하는 열에, 이미 다른 행에서 퀸을 위치시켰다면, 그 위치는 불가능
7.
또한 위치시키고자 하는 열의 대각선에 퀸이 위치해도 불가능함을 고려한다
#include <iostream>
#define MAX 15
using namespace std;
int N, total = 0;
int col[MAX] = { 0 };
bool check(int level) {
for (int i = 0; i < level; i++) {
if (col[i] == col[level] || abs(col[level] - col[i]) == level - i) {
return false;
}
}
return true;
}
void nqueen(int x) {
if (x == N) total++;
else {
for (int i = 0; i < N; i++) {
col[x] = i;
if (check(x)) nqueen(x+1);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
nqueen(0);
return 0;
}
C++
복사
