[백준 C++] 9663 N-Queen - 백트래킹

9663번: N-Queen

cpp

#include <iostream>
using namespace std;

int N, Cnt;
int Col[14];

bool Check(int Index)
{
‌for (int i = 0; i < Index; ++i)
‌{
‌‌if (Col[i] == Col[Index]
‌‌‌|| abs(Col[Index] - Col[i]) == Index - i)
‌‌{
‌‌‌return false;
‌‌}
‌}

‌return true;
}

void DFS(int Index)
{
‌if (Index == N)
‌{
‌‌++Cnt;
‌‌return;
‌}

‌for (int i = 0; i < N; ++i)
‌{
‌‌Col[Index] = i;
‌‌if (Check(Index))
‌‌{
‌‌‌DFS(Index + 1);
‌‌}
‌}
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌cin >> N;
‌DFS(0);
‌cout << Cnt;
}

---

 

DFS & 백트래킹을 이용해서 N개의 퀸을 놓을 수 있는 모든 경우를 탐색하는 문제입니다.

주의할 점은 2차원 배열로 풀면 시간초과가 발생합니다.

 

따라서 각 열 마다 어느 행에 퀸을 배치할 것인지를 저장하는 1차원 배열로 풀어야 합니다.

깊이 우선 탐색으로 각 열 마다 놓을 수 있는 행에 퀸을 배치해가면서 모든 경우를 탐색해주면 됩니다.

 

놓을 수 있는 행을 체크하는 조건은 다음과 같습니다.

1. 다른 열의 퀸과 행이 겹치지 않아야 함: Col[i] != Col[Index]

2. 다른 열의 퀸과 대각선으로 겹치지 않아야 함: abs(Col[Index] - Col[i]) != Index - i