문제
참고
https://chanhuiseok.github.io/posts/baek-1/
https://cryptosalamander.tistory.com/58
https://wooono.tistory.com/302
해당 문제는 입력 N에 대해 N*N 체스판 위에 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수를 출력하는 문제이다.
먼저, 해당 문제를 풀기 위해 체스에서 퀸의 이동 범위에 대해 찾아봤는데, 상하좌우와 대각선을 포함한 8개 방향에 대해 거리 제한 없이 움직일 수 있는 말이었다.
처음에는 체스판과 퀸에 대한 특징을 이해하지 못한 채, 문제를 풀기 위해 2차원 배열 체스판과 check 배열을 선언하여 두 2차원 배열에 대한 완전탐색 코드를 구현했다.
하지만 백준 사이트에 채점을 돌려볼 필요도 없이, 완전탐색 과정에서 모든 배열을 최대한 call by reference로 했음에도, 로컬 환경에서부터 N이 5이상이 될 수록 시간이 굉장히 많이 걸리는 것을 확인할 수 있었다.
따라서 위의 여러 사이트를 통해 새로운 접근법을 생각하여 다시 코드를 구현했다.
-
가장 먼저, N*N 체스판에 N개의 퀸을 배치하기 위해, 위에서 말한 퀸이 움직일 수 있는 경로를 고려하면,
최소한 같은 행(열)에 두 개 이상의 퀸을 놓을 수 없다는 것을 알 수 있다.
같은 행(열)에 이미 있는 퀸의 공격 경로에 배치하는 것이기 때문이다.따라서 매 행(혹은 열)에 하나의 퀸을 놓는다고 생각하고, 이를 위해 1차원 배열을 활용했다.
-
1번을 통해 이미 배치된 퀸의 상하좌우 경로는 고려할 수 있지만, 대각선 방향에 대한 경로는 고려할 수 없다.
이를 위해 대각선 방향의 경우 |x2 - x1| == |y2 - y1| 관계를 활용한다.
따라서, 반복문을 통해 이미 배치되어 있는 모든 퀸과 새로운 행에서 배치하려는 열 위치를 비교하여 배치가 가능한 열에 놓는다.
그리고 재귀를 통해 매 행에 대해 위와 같은 과정을 반복한다. -
이전에는 백트래킹과 완전탐색에 대한 차이를 제대로 인지하지 못한 채, 2차원 check 배열을 통해 체스판에 퀸을 놓을 수 있는 모든 경우를 고려했다.
따라서 결과적으로 N*N 체스판에 퀸이 N-1개가 놓이는(고려할 필요가 없는) 경우까지 모두 고려하여 많은 연산 시간을 유발했다.(완전탐색)이러한 문제를 해결하기 위해 1번에서 작성한 특징을 활용해, 탐색할 가치가 있는 경우에만(가지치기) DFS 탐색을 하도록 코드를 구현했다. 세부 로직은 다음과 같이 구성했다.
1) for 문을 통해 매 행마다 놓을 위치(=열)에서 이미 배치된 퀸에 대해 1번 규칙을 만족하는지 모두 확인한다.
2) 모두 만족하는 경우 해당 위치(=열)에 퀸을 배치한다.
3) 재귀호출을 하여 다음 행에 대해 반복한다.기존에는 항상 DFS를 활용한 완전탐색을 토대로 코드를 구현했기 때문에, 재귀호출 과정에서 이미 탐색한 경우의 check를 풀어주지 않는 코드의 구성이 낯설고 잘 이해가 되지 않았다.
하지만 완전탐색과 백트래킹의 차이를 이해하고, 코드 구조를 보니 아래의 코드와 같은 구조로 구현한 백트래킹 구조가 이해됐다.
가장 핵심이 된 내용은, 이전에 완전탐색을 할 때처럼 2차원 배열을 통해 백트래킹을 하는 것이 아니라 1차원 배열을 통해 각 행에 배치할 열 만을 고려하는 것이기 때문에, check를 풀어주는 과정 없이 for 문 내에 위치한 row[L] = i; 을 통해 값을 없데이트 해주는 것 만으로도 충분했다.
참고로 이러한 방법으로 구현한 코드의 시간복잡도는 O(N^3)으로, 문제의 요구사항을 충분히 만족할 수 있다.
문제를 푸는 과정에서 어렵게 느껴졌고, 구글링을 통해 풀이법을 깨닫고는 되게 허탈했던 만큼 복기를 위한 포스트가 절반은 일기장? 같은 느낌으로 작성됐지만, 백트래킹에 대해 제대로 이해할 수 있었기 때문에 많이 유익한 문제였다.
특히, 많은 백트래킹 유형 문제를 풀면서 위와 같이 다양한 구조로 완전탐색 혹은 백트래킹을 구현하는 경험이 필요한 것 같다.
위의 내용을 정리한 코드는 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int n, cnt;
vector<int> row(15);
bool check(int L, int col) {
for (int i = 0; i < L; i++) {
if (col == row[i]) {
return false;
}
if ((L - i) == abs(col - row[i])) {
return false;
}
}
return true;
}
void DFS(int L) {
if (L == n) {
cnt++;
}
else {
for (int i = 0; i < n; i++) {
if (check(L, i)) {
row[L] = i;
DFS(L + 1);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt", "rt", stdin);
cin >> n;
DFS(0);
cout << cnt << "\n";
return 0;
}