문제 이해 단계
https://www.acmicpc.net/problem/9663
NxN짜리 체스판에 N개의 퀸을 서로 공격하지 못하게 둔다.
N이 주어졌을 때 이 경우의 수를 구하는 문제
문제 접근 단계
퀸이 움직일 수 있는 경로는 위와 같다.
퀸을 정가운데 놨을 때, 노란색 영역에는 퀸을 두면 안 된다
제한사항부터 알아보면, N은 최대 14까지 가능하다.이 말은 맵은 14x14까지,
체스 말은 14개까지 가능하다는 것이다.
N이 상당히 작기 때문에 완전탐색이 가능할 것 같다.
N개의 퀸을 체스판에 두는 모든 경우의 수를 구해야 하기 때문에, 퀸을 모든 곳에 둬서 판단하는 방법밖에 없다.
그런데 일반적인 백트래킹으로 이를 확인하기에는, 최대 14^14로 대략 100억이 넘어간다.(시간 초과)
그래서 2차원배열로 백트래킹을 진행하는 것이 아닌, 1차원 배열로 시간을 줄이도록 한다.
1차원 백트래킹 과정
N = 4일 때의 예시이다. 백트래킹을 횡단 위로 진행한다.
한 행의 어떤 열을 고르면 바로 다음 열로 넘어간다.
고를 수 있는 열이 있다면 또 특정 열을 고른 다음다음 행으로 넘어간다.
이러한 과정을 1행의 마지막 열까지 반복한다.
여기서 1차원배열로 나타내기 위해 인덱스를 행, 값을 열로 나타낸다.
예를 들어 4행 2열은 arr [4] = 2 이런 식으로 나타낸다.
자세한 구현은 문제 구현 단계에서 보자.
문제 구현 단계
#include <iostream>
#include <cmath>
using namespace std;
int N;
int ans = 0;
int col[15] = {0,};
// 해당 위치에 퀸을 놓을수 있는지 없는지 확인하는 함수
bool isPossible(int num){
for(int i = 0; i < num; i++){
// 같은 열, 대각선에 있으면 안됨
if(col[num] == col[i] ||
abs(num-i) == abs(col[num]-col[i])) return false;
}
return true;
}
// 백트래킹을 진행
void backTracking(int cIdx){
// 마지막행까지 도달했다면 N개의 퀸을 모두 놓은 것이므로 성공
if(cIdx == N){
ans++;
return;
}
for(int i = 0; i < N; i++){
col[cIdx] = i; // cIdx 행 i열에 퀸을 둠(cIdx,i)
if(isPossible(cIdx)){
// 해당 위치에 놓을 수 있으면 다음 행으로 넘어감
backTracking(cIdx+1);
}
// 그렇지 않으면 다음 열에 놓는 것으로 다시 판단
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
backTracking(0);
cout << ans;
}isPossible로 해당 행과 열에 퀸을 놓을 수 있는지 없는지를 판단한다.
여기서 매개변수는 행의 번호를 뜻한다.
행의 번호만 알고 있다면 그에 할당된 열의 번호를 알 수 있다.
위 주석과 같이 여태까지 배치한 퀸이 세로에 있는지, 대각선에 있는지를 확인해 준다.
backTracking() 함수에서는 매개변수 cIdx를 받는데, 이는 이번에 판단할 행의 번호를 의미한다.
이 인덱스가 N과 같다는 뜻은 모든 N개의 퀸을 다 배치했다는 뜻이므로 성공을 의미한다.
따라서 백트래킹을 종료해 주고, 성공 횟수+1을 해준다.
백트래킹에서 검사하는 것은 간단하다.
cIdx에 해당하는 행에서 1 번열부터 하나씩 두면서 해당 칸에 퀸을 둘 수 있는지 체크한다.
그 칸에 둘 수 있으면 cIdx+1로 다음 행으로 넘어간다.
그렇게 cIdx 마지막 N번째 행까지 배치를 하게 되면 성공하게 되는 것이다.
여기까지가 핵심적인 코드 설명의 끝이다.
시행착오
백트래킹 함수의 대표적인 문제라던데, 나는 이제야 이 문제를 풀어봤다.
제한시간이 10초라서 시간이 엄청 넉넉할 줄 알았는데 그렇지도 않았다.
처음에는 DP인 줄 알고 DP로 접근하다가 문제 유형을 보고, 백트래킹으로 풀기 시작했다.
1차원배열은 상상도 못 했고, 2차원배열로 백트래킹을 하다 보니
어떻게 최적화해도 시간초과가 떠서 결국엔 인터넷을 참고했다.
이런 방식으로 백트래킹을 할 수 있구나. 역시 대표문제답다.
생활비..