N Queen은 한 변의 길이가 N칸인 체스판에 가로, 세로, 대각선으로 움직일 수 있는 퀸 N개가 서로 잡을 수 없도록 배치하는 문제이다. 배치는 여러 경우가 가능하며, 가능한 배치의 수를 출력하는 것이 이 문제의 목표이다. 예를 들어, N = 4일 때 가능한 배치는 2가지이다.
N Queen은 대표적인 dfs 탐색 예제로, 간단한 dfs 구현을 사용해 풀이한다. DFS란 깊이 우선 탐색 (depth-first search)으로, 더 깊어지는 방향으로 탐색을 진행한다. 이진 트리에서 부모 노드에서 자식 노드로 계속해서 깊게 들어가는 방향으로 탐색하고, 더 이상 갈 노드가 없으면 그때 빠져나와 다른 노드로 이동한다. 이와 상반되는 개념이 BFS(Breadth-first search) 넓이 우선 탐색으로, 시작 노드에서 가까운 노드 순으로 이동한다.
아래는 내가 예전에 DFS, BFS에 대해 설명한 글이다. (가독성이 떨어진다)
너비 우선 탐색(BFS, breadth-first search)는 시작 정점을 방문한 후 시작 정점과 인접한 모든 정점을 방문하는 방식으로 진행된다. 시작 정점과 인접한 모든 정점을 반복했으면, 이제 그 정점에서 또 인접한 정점들을 방문한다. 이 과정은 더 이상 방문하지 않은 지점이 없을 때까지 반복된다. 이러한 너비 우선 탐색은 최단 경로를 찾는 것을 보장해주며, 최단 경로를 찾아야 할 때 자주 사용된다. 너비 우선 탐색의 경우 큐를 사용해 이진 트리에서 정점 순서대로 정점을 배열할 수 있다. ‘큐’는 컴퓨터의 기본 자료 구조 중 하나로, 먼저 들어간 데이터가 먼저 나오는 FIF0(first in first out)의 구조이다. 다음 그림과 같이 양쪽 끝이 다 뚫려있는 터널을 생각하면 쉽다. 방문한 정점을 다음과 같은 터널 구조의 큐에 넣어 방문 처리를 해주고, 그 정점과 인접한 정점들도 차례로 다 큐에 집어넣고 방문처리를 해준다. 방문처리를 하지 않은 인접한 노드가 더 이상 없으면, 그 노드를 들어온 입구와 반대쪽에 위치한 출구로 빼낸다. 이런 과정을 반복하면 노드들은 인접한 순서대로 큐에 들어갔다가 다시 나와서 순서대로 정렬된다. 이때 노드들의 정렬된 순서가 바로 최단 경로이다.
깊이 우선 탐색(DFS, depth-first search)도 역시 맹목적 탐색방법의 하나이다. 다만 깊이 우선 탐색의 경우 큐 대신 한쪽 끝이 막혀있는 터널형의 자료구조인 ‘스택’을 사용한다. 스택은 먼저 들어간 노드가 나중에 나오는 FIFL(first in first last)의 구조를 지닌다. 인접한 자식 노드(트리에서 자신과 인접해있으며, 자신보다 시작 노드에서 먼 노드, 이진 트리에서는 한 노드당 2개씩 지닌다.)가 도달하고자 하는 목표노드일 때까지 첨가한다. 이때 너무 깊게 탐색하는 것을 막기 위해 깊이 제한을 두고, 깊이 제한에 도달했을 경우 다시 위로 올라가며 살피지 않는 노드들을 살피는 백트래킹을 실행한다. 스택에 첨가한 노드는 첨가 즉시 방문처리가 완료된다. 더 이상 인접한 노드가 없으면 노드들을 늦게 들어온 순으로 빼낸다. 이렇게 스택에서 모든 노드가 빠지고, 방문처리된 순서가 결과로 리턴된다.
#include <stdio.h>
int arr[15][15];
int n;
int ans = 0;
void dfs(int step){
if(step > n){
ans++;
return;
}
for(int i = 1; i<= n; i++){
if(arr[step][i] >= 1){
continue;
}
arr[step][i] = 1;
for(int j = 1; j<= n; j++){
if(j != i){
arr[step][j]++;
}
if(j != step){
arr[j][i]++;
}
if((step + j <= n) && (i + j <= n)){
arr[step+j][i+j]++;
}
if((step + j <= n) && (i - j >= 1)){
arr[step+j][i-j]++;
}
if((step - j >= 1) && (i - j >= 1)){
arr[step-j][i-j]++;
}
if((step - j >= 1) && (i + j <= n)){
arr[step-j][i+j]++;
}
}
dfs(step+1);
arr[step][i]--;
for(int j = 1; j<= n; j++){
if(j != i){
arr[step][j]--;
}
if(j != step){
arr[j][i]--;
}
if((step + j <= n) && (i + j <= n)){
arr[step+j][i+j]--;
}
if((step + j <= n) && (i - j >= 1)){
arr[step+j][i-j]--;
}
if((step - j >= 1) && (i - j >= 1)){
arr[step-j][i-j]--;
}
if((step - j >= 1) && (i + j <= n)){
arr[step-j][i+j]--;
}
}
}
}
int main(void){
scanf("%d", &n);
dfs(1);
printf("%d", ans);
}