N-Queen 문제는 백트래킹의 가장 대표적인 예제로서, 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다. 즉 이 문제를 풀기 위해서 N*N짜리 배열을 직접 만들 필요 없이,
크기가 N인 일차원 배열을 만든 후, 각 열에 몇번째 행의 퀸이 있는지를 저장하면 된다.
예를 들어 N = 4일때,
일차원 배열 col [] 에 이런식으로 저장하면 된다.
col[0] = 0번째 열에 존재하는건 1행의 퀸이므로 1 저장
col[1] = 1번째 열에 존재하는건 3행의 퀸이므로 3 저장
col[2] = 2번째 열에 존재하는건 0행의 퀸이므로 0 저장
col[3] = 3번째 열에 존재하는건 2행의 퀸이므로 2 저장
그후 한 행씩 퀸을 배치해가면서 총 배치 행수가 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좌표의 차이가 일정한 값을 가질 경우 해당 퀸과 대각선에 있다고 판단할 수 있다.
이해가 잘 안간다면 코드를 보면 이해할 수 있을 것이다.
코드
#include <iostream>
#define MAX 15
using namespace std;
int col[MAX];
int N, total = 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;
//col[i]가 의미하는 것이 X좌표, i가 의미하는것이 Y좌표이므로 차이가 일정하다면 대각선에 있다고 볼 수 있다.
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() {
cin >> N;
nqueen(0);
cout << total;
}
평가
가장 기본적인 예제이지만 난이도가 쉽지 않은 문제이다.
백트래킹에 대한 충분한 이해가 있어야 풀이가 가능하다.
또한, 대각선을 판별하는 식을 얼마나 효율적으로 작성할 수 있느냐에 따라서 실행시간이 크게 달라지기 때문에, 시간초과가 발생하지 않기 위해서는 2차원배열보다는 단순히 1차원배열을 활용한 진위판별을 하는 것이 필요한 문제이다.
