득이공간
[백준 C++] 9663 N-Queen - 백트래킹 본문
#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
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 11054 가장 긴 바이토닉 부분 수열 - 다이나믹프로그래밍 (0) | 2024.03.12 |
---|---|
[백준 C++] 9935 문자열 폭발 - 문자열 (0) | 2024.03.11 |
[백준 C++] 2448 별 찍기 - 11 - 재귀 (1) | 2024.03.07 |
[백준 C++] 31498 장난을 잘 치는 토카 양 - 이분탐색 (0) | 2024.03.07 |
[백준 C++] 1987 알파벳 - 백트래킹 (1) | 2024.03.06 |