도입
이 글은 모든 경우의 수를 찾는 상황에서 사용할 수 있는 백트래킹 (Backtracking) 에 대한 개념 설명을 담고 있습니다. 재귀를 배운 이후에 같이 배우면 좋은 이 백트래킹 알고리즘은 브루트포스와는 다르게, 여러 경우의 수를 조건에 맞게끔 깊게 구해낼 수 있습니다. 재귀를 사용하므로 코드도 간단하게 작성할 수 있어서, 익히게 된다면 재밌게 문제를 해결할 수 있다고 생각합니다. 입력 제한이 큰 경우에는 시간복잡도가 지수적으로 증가하는 백트래킹보다 그리디나 DP를 사용하는 것이 효율적이겠지만, 백트래킹만이 빠르게 문제 상황을 해결할 수 있는 상황도 존재합니다. 백트래킹의 기본 원리를 익히고 예제 문제와 함께 이해하는 것이 이 글의 목표입니다.
본 글은 C를 기반으로 작성되었습니다.
다음 알고리즘에 대한 이해가 필요합니다!
재귀 (Recursion) : https://readytojoin.tistory.com/83
스택 (Stack) : https://readytojoin.tistory.com/35
깊이 우선 탐색과 너비 우선 탐색 (Depth-First Search & Breadth-First Search) : https://readytojoin.tistory.com/80
접근
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
다음과 같은 문제를 예시로 들어보자.
퀸 N 개를 동시에 배치할 수 있는 경우의 수
크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 퀸은 자신의 위치를 기준으로 가로, 세로, 대각선 상에 위치한 칸에서 아무 위치든 자유롭게 이동할 수 있는 기물이다. 해당 문제를 해결하기 위해선 어떻게 해야할까? 퀸을 배치할 때마다 체스판에 표시하고, 다른 퀸을 배치할 때 체스판을 전체적으로 탐색해보면서 기존에 배치한 퀸의 이동 경로에 들어가는 지를 확인해야 할까?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int flag = 1;
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
if (map[y][x] == 1 && (i == y || j == x || i+j == y+x || -i+j == -y+x)) {
flag = 0;
}
}
}
if (flag == 1) map[i][j] = 1; // New Queen!
}
}
단순 반복문으로만 해결하려면 퀸 1개를 배치하는 코드부터 4중 반복문을 써야 할테고, 다른 퀸을 놓을 때라던가, 이 칸 말고 다른 칸에도 배치했을 때 등등 여러 경우의 수를 구해야 하니 머리가 복잡해질 것이다. 전부 계산한다면 O(N^N) 으로 엄청난 양의 조합을 고려해야 할 것이다.
이 문제를 재귀를 활용한 백트래킹으로 풀이해보자.
백트래킹 ( Backtracking )
백트래킹은 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 후보를 나열하여 조건을 점진적으로 체크하며, 조건이 맞지 않으면 뒤로 돌아가 다른 후보를 선택하면서 (Backtrack) 최적 해를 찾아가고, 최종적으로 모든 경우의 수를 찾아낼 수 있는 전략 알고리즘이다. 퇴각 검색 알고리즘이라고도 불린다.
현재 상태에서 다음 상태로 나아갈 수 있는 모든 경우를 찾아서 탐색하고, 제약 조건에 맞지 않다면 이전 상태로 돌아가 이전 상태에서의 다음 상태로 나아갈 수 있는 나머지 경우를 찾아서 탐색하고........... 이를 반복하여 조건에 맞지 않는 경우는 제외하고 모든 경우를 찾아낸다.
실제 구현할 때는 선택할 후보들을 상태 공간 트리 (state-space-tree) 를 이용해 표현하여 DFS로 탐색을 진행하고, 다음과 같은 용어를 사용한다고 한다.
- Pruning (가지치기) : 조건에 맞지 않으면 포기하고 이전 상태로 돌아간다.
- Promising : 현재 상태가 조건에 맞는지 검사한다.
예를 들자면 다음과 같다, 현재 체스판에는 (2, 2) 에 퀸 하나가 놓여있고, 이를 퀸 한 개를 배치한 상태라고 하겠다. 새로운 퀸을 (0, 0) 에 배치했다고 했을 때, 현재 상태가 조건에 맞는지 검사하는 Promising 을 진행하고, 새로운 퀸은 이전의 퀸 경로와 겹치니 Pruning 을 진행하여 이 퀸을 배치하지 않는다. 따라서 퀸 한 개를 배치한 상태로 돌아간다.
다시 (2, 2) 에 퀸 한 개를 배치한 상태로 돌아와서, 새로운 퀸을 (0, 1) 에 배치했다고 한다면, 현재 상태가 조건에 맞는지 검사하는 Promising 을 진행하고, 기존 퀸의 이동 경로와 겹치지 않으니 지금 이 상태 (퀸 두 개를 배치한 상태)에서 또 다른 퀸을 배치할 수 있는 경우를 탐색하기 시작한다.
이렇게 Promising과 Pruning 을 반복적으로 진행하다보면, 퀸 두 개를 배치한 상태에서 퀸 세 개를 배치한 상태를 찾을 수도 있고, 퀸 세 개를 배치한 상태에서 또 Pruning 이 실행되어 퀸 두 개를 배치한 상태로 돌아가 다시 찾을 수 있고.... 진행될수록 모든 제약 조건에 맞아가면서 퀸 N 개를 배치한 상태에 도달하게 되고, 우리가 원하는 케이스 중 하나를 얻게 될 수 있다!
한 상태에서 다음 상태로 진행하기 위한 모든 경우를 탐색하다 보니, 시간 복잡도가 지수꼴인 경우가 많다.
백트래킹 - DFS 를 이용한 기본 원리 익히기
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
기본 원리를 위해, 가장 쉬운 백트래킹 연습 문제를 예시로 들어보자. 1부터 3까지 자연수 중에서 중복 없이 3개를 고른 수열을 찾는다고 가정한다.
우리가 시각적으로 경우의 수를 모두 찾는다고 가정할 때, 중복 없이 3개를 고르는 구조를 다음과 같은 트리 구조로 나타낼 수 있다.
또한, 1부터 4까지 자연수 중에서 중복 없이 3개를 고른 수열을 찾을 때의 상태 현황을 트리로 나타내면 다음과 같다.
백트래킹은 현재 상태 (노드) 에서 갈 수 있는 모든 경우를 탐색하려고 노력한다. 지금 이 문제는 중복 없이 수를 고르기에 선택지가 줄어들지만, 중복 없이 수를 고를 수 있다면 지금보다 갈 수 있는 상태가 더욱 많을 것이다. 이러한 모든 상황을 DFS 로 전체 탐색하여, 리프 노드에 도달할 때마다 카운트를 해준다면 원활하게 문제를 해결할 수 있다.
그럼 먼저, 첫 번째 수를 고를 때 1을 고르는, 2를 고르는.... 이러한 상태부터 시작해보자.
사용하는 변수, 함수를 먼저 소개한다.
int n, m; // 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열 찾기
int stack[MAX_NUM]; // 현재 상태에서 선택된 수들 ( 스택 )
int stack_size = 0;
void push(int x) { if (stack_size != MAX_NUM) stack[stack_size++] = x; }
void pop() { if (stack_size) stack_size -= 1; }
int visited[MAX_NUM+1] = {0,}; // 지금 i 번째 수를 이미 골랐다면 -> visited[i] = 1
// 지금 i 번째 수를 고르지 않았다면 -> visited[i] = 0현재 상태에서 고른 숫자들의 데이터가 stack 배열에 들어가게 될거고, push 와 pop 함수로 관리할 것이다.
현재 상태에서 i번의 수를 골랐는지 고르지 않았는지를 빠르게 파악하기 위해, visited 배열을 이용한다.
void dfs() {
}
int main(void) {
scanf("%d %d", &n, &m);
dfs();
return 0;
}그리고, DFS 를 진행하기 위해 DFS 함수를 만들어 이 곳에서 백트래킹을 진행할 예정이다.
필자는 Promising 과 Pruning 을 굳이 구현하기 보다는, 재귀 함수를 구현하는 것처럼 종료 조건을 먼저 설정하고 탐색을 진행할 때 조건을 설정하는 편인데, 함수를 더 작성하는 것보단 DFS 함수 하나로 해결하는 것이 편하여 이 방법으로 설명할 예정이다.
void dfs() {
if (stack_size == m) {
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("\n");
return;
}
}먼저, m 개의 수를 전부 다 골라 스택에 저장되어 있다면, 스택에 있는 데이터들을 전부 출력하고 함수를 반환한다. 함수를 반환하면 이전 상태로 돌아가서 나머지 상태를 탐색해야 한다. 즉, 끝까지 수를 다 고른 상태이니 Pruning이 진행되는 것이다.
void dfs() {
if (stack_size == m) {
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) { // 해당 수를 고르지 않았다면 고른 다음 다음 상태로
}
}
}종료 조건을 만족하지 않았다면, 1부터 N까지의 수 중 어떤 수를 선택할 지 골라야 한다. 이미 그 수를 현재 상태에 골랐는지는 visited[i] 를 이용해 확인한다. 해당 수를 고르지 않았다면, 이 수를 고른 다음 상태로 진입해야 한다.
다음 상태로 넘어가기 위한 조건이 되니, Promising 과 같은 역할을 한다고 할 수 있겠다.
void dfs() {
if (stack_size == m) {
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) { // 해당 수를 고르지 않았다면 고른 다음 다음 상태로
visited[i] = 1;
push(i);
dfs();
pop();
visited[i] = 0;
}
}
}
먼저 다음 상태로 넘어가기 위해, visited[i] 를 1로 설정해주고 stack 에 i번 수를 쌓는다. 그리고 함수를 다시 호출한다.
여기서 중요한 점은, 다시 호출한 함수가 종료되었을 때 넣은 i번 수를 빼고 visited[i] 를 다시 0으로 설정하는 것이다.
함수를 다시 호출했는데 그 함수가 종료되었다는 것은, 다음 상태로 넘어가서 거기서 진행할 수 있는 탐색의 모든 경우를 보고 지금 상태로 다시 돌아왔다는 신호이다. 지금 상태로 다시 돌아와야 하니 i 번을 고르지 않은 상태로 복구시켜줘야, i번이 아닌 i+1 번을 고른 상태로 또 다음 상태에 진입할 때 사용할 수 있기 때문이다.
1을 고른 상태에서, 2를 골라야 하니 visited[2] = 1, push(2) 를 진행해준 다음 dfs() 를 진행한다면?
-> 1, 2를 고른 상태에서 3을 고르고, 4를 고르고.... 를 진행하며 안쪽까지 탐색한 뒤
다시 1을 고른 상태로 돌아올 것이다. 그 후 2가 아닌 1과 3을 고른 상태를 탐색해야 한다.
따라서 2를 고르지 않은 것처럼 2에 대한 정보를 없앤다. 없애지 않으면 다음 상태는 (1, 3)을 골라야 하는데 그냥 3이 들어가버려 (1, 2, 3) 이 되어버릴 수도
1에서는 2, 3, 4 를 고르는 상태를 반복하면서 볼테니, (1, 2) 를 고른 상태를 탐색했다면 (1, 3) 을 고른 상태를 탐색하고, (1, 4) 를 고른 상태까지 탐색을 마무리 하면 이제 1을 첫 번째로 고른 상태에 대한 탐색은 종료하고 2를 첫 번째로 고른 상태 탐색을 시작할 것이다. 이렇듯 현재 상태에서 할 수 있는 모든 탐색을 하고 돌아오는 것이 주 목표이다.
빠른 이해를 위해 디버깅을 진행해보자.
Now Stack : [ ] (0)
Select 1
Now Stack : [ 1 ] (1)
Select 2
Now Stack : [ 1 2 ] (2)
Select 3
Now Stack : [ 1 2 3 ] (3)
Complete M -> Pruning
Delete 3
Select 4
Now Stack : [ 1 2 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 2
Select 3
Now Stack : [ 1 3 ] (2)
Select 2
Now Stack : [ 1 3 2 ] (3)
Complete M -> Pruning
Delete 2
Select 4
Now Stack : [ 1 3 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 3
Select 4
Now Stack : [ 1 4 ] (2)
Select 2
Now Stack : [ 1 4 2 ] (3)
Complete M -> Pruning
Delete 2
Select 3
Now Stack : [ 1 4 3 ] (3)
Complete M -> Pruning
Delete 3
Delete 4
Delete 1
Select 2
Now Stack : [ 2 ] (1)
Select 1
Now Stack : [ 2 1 ] (2)
Select 3
...재귀를 이용해 수를 추가하고 제거함을 반복하여 모든 경우의 수를 DFS 재귀로 탐색하는 원리를 확인할 수 있다. 중요한 점은 다음 상태를 고른 것처럼 정보를 업데이트한 뒤 재귀 함수를 호출하고, 호출한 재귀 함수가 종료되면 나머지 상태를 탐색하기 위해 방금 업데이트한 정보를 지우는 것이다.
- 출력 전문
- 사용 함수
void dfs() {
printf("Now Stack : [ ");
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("] (%d)\n", stack_size);
if (stack_size == m) {
printf("Complete M -> Pruning\n");
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) { // 해당 수를 고르지 않았다면 고른 다음 다음 상태로
printf("Select %d\n", i);
visited[i] = 1;
push(i);
dfs();
printf("Delete %d\n", i);
pop();
visited[i] = 0;
}
}
}
- 출력 (입력 : 4 3)
Now Stack : [ ] (0)
Select 1
Now Stack : [ 1 ] (1)
Select 2
Now Stack : [ 1 2 ] (2)
Select 3
Now Stack : [ 1 2 3 ] (3)
Complete M -> Pruning
Delete 3
Select 4
Now Stack : [ 1 2 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 2
Select 3
Now Stack : [ 1 3 ] (2)
Select 2
Now Stack : [ 1 3 2 ] (3)
Complete M -> Pruning
Delete 2
Select 4
Now Stack : [ 1 3 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 3
Select 4
Now Stack : [ 1 4 ] (2)
Select 2
Now Stack : [ 1 4 2 ] (3)
Complete M -> Pruning
Delete 2
Select 3
Now Stack : [ 1 4 3 ] (3)
Complete M -> Pruning
Delete 3
Delete 4
Delete 1
Select 2
Now Stack : [ 2 ] (1)
Select 1
Now Stack : [ 2 1 ] (2)
Select 3
Now Stack : [ 2 1 3 ] (3)
Complete M -> Pruning
Delete 3
Select 4
Now Stack : [ 2 1 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 1
Select 3
Now Stack : [ 2 3 ] (2)
Select 1
Now Stack : [ 2 3 1 ] (3)
Complete M -> Pruning
Delete 1
Select 4
Now Stack : [ 2 3 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 3
Select 4
Now Stack : [ 2 4 ] (2)
Select 1
Now Stack : [ 2 4 1 ] (3)
Complete M -> Pruning
Delete 1
Select 3
Now Stack : [ 2 4 3 ] (3)
Complete M -> Pruning
Delete 3
Delete 4
Delete 2
Select 3
Now Stack : [ 3 ] (1)
Select 1
Now Stack : [ 3 1 ] (2)
Select 2
Now Stack : [ 3 1 2 ] (3)
Complete M -> Pruning
Delete 2
Select 4
Now Stack : [ 3 1 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 1
Select 2
Now Stack : [ 3 2 ] (2)
Select 1
Now Stack : [ 3 2 1 ] (3)
Complete M -> Pruning
Delete 1
Select 4
Now Stack : [ 3 2 4 ] (3)
Complete M -> Pruning
Delete 4
Delete 2
Select 4
Now Stack : [ 3 4 ] (2)
Select 1
Now Stack : [ 3 4 1 ] (3)
Complete M -> Pruning
Delete 1
Select 2
Now Stack : [ 3 4 2 ] (3)
Complete M -> Pruning
Delete 2
Delete 4
Delete 3
Select 4
Now Stack : [ 4 ] (1)
Select 1
Now Stack : [ 4 1 ] (2)
Select 2
Now Stack : [ 4 1 2 ] (3)
Complete M -> Pruning
Delete 2
Select 3
Now Stack : [ 4 1 3 ] (3)
Complete M -> Pruning
Delete 3
Delete 1
Select 2
Now Stack : [ 4 2 ] (2)
Select 1
Now Stack : [ 4 2 1 ] (3)
Complete M -> Pruning
Delete 1
Select 3
Now Stack : [ 4 2 3 ] (3)
Complete M -> Pruning
Delete 3
Delete 2
Select 3
Now Stack : [ 4 3 ] (2)
Select 1
Now Stack : [ 4 3 1 ] (3)
Complete M -> Pruning
Delete 1
Select 2
Now Stack : [ 4 3 2 ] (3)
Complete M -> Pruning
Delete 2
Delete 3
Delete 4
다음은 사용한 코드 전문이다.
#include <stdio.h>
#define MAX_NUM 10
int n, m; // 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열 찾기
int stack[MAX_NUM]; // 현재 상태에서 선택된 수들 ( 스택 )
int stack_size = 0;
void push(int x) { if (stack_size != MAX_NUM) stack[stack_size++] = x; }
void pop() { if (stack_size) stack_size -= 1; }
int visited[MAX_NUM+1] = {0,}; // 지금 i 번째 수를 이미 골랐다면 -> visited[i] = 1
// 지금 i 번째 수를 고르지 않았다면 -> visited[i] = 0
void dfs() {
if (stack_size == m) {
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) { // 해당 수를 고르지 않았다면 고른 다음 다음 상태로
visited[i] = 1;
push(i);
dfs();
pop();
visited[i] = 0;
}
}
}
int main(void) {
scanf("%d %d", &n, &m);
dfs();
return 0;
}
이제 백트래킹을 문제에 적용해보자.
15650 : N과 M (2)
https://www.acmicpc.net/problem/15650
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
N과 M (1) 문제와 같지만, 고른 수열은 오름차순이어야 한다.
현재 상태에서 가장 마지막으로 고른 수보다 1 높은 수부터 찾기를 시작하면 된다.
백트래킹을 이용해 오름차순으로 저장하는 것은 꽤 많이 이용하는 아이디어이므로 익숙해지면 좋다.
#include <stdio.h>
#define MAX_NUM 10
int n, m; // 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열 찾기
int stack[MAX_NUM]; // 현재 상태에서 선택된 수들 ( 스택 )
int stack_size = 0;
void push(int x) { if (stack_size != MAX_NUM) stack[stack_size++] = x; }
void pop() { if (stack_size) stack_size -= 1; }
int visited[MAX_NUM+1] = {0,}; // 지금 i 번째 수를 이미 골랐다면 -> visited[i] = 1
// 지금 i 번째 수를 고르지 않았다면 -> visited[i] = 0
void dfs() {
if (stack_size == m) {
for (int i = 0; i < stack_size; i++) printf("%d ", stack[i]);
printf("\n");
return;
}
int start = 1;
if (stack_size) start = stack[stack_size - 1] + 1;
for (int i = start; i <= n; i++) {
if (visited[i] == 0) { // 해당 수를 고르지 않았다면 고른 다음 다음 상태로
visited[i] = 1;
push(i);
dfs();
pop();
visited[i] = 0;
}
}
}
int main(void) {
scanf("%d %d", &n, &m);
dfs();
return 0;
}
9653 : N-Queen
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
가로, 세로, 대각선에 이미 퀸이 배치되어 있다면 배치할 수 없다.
N x N 체스판을 전부 돌면서 해당 칸에 퀸을 배치할 수 있는지 확인하는 방법도 있지만, 일단 몇 조건을 축약할 수 있다.
1. 퀸은 한 행에 한 개만 배치할 수 있으므로, N x N 체스판에 N 개의 퀸은 행마다 한 개씩 배치할 수 있다.
2. 퀸은 한 열에 한 개만 배치할 수 있으므로, N x N 체스판에 N 개의 퀸은 열마다 한 개씩 배치할 수 있다.
3. 퀸은 한 대각선 (왼쪽 아래 <-> 오른쪽 위 방향) 에 한 개만 배치할 수 있다.
4. 퀸은 다른 대각선 (왼쪽 위 <-> 오른쪽 아래 방향) 에 한 개만 배치할 수 있다.
편의를 위해 3번 조건의 대각선을 1번 대각선 ( / ), 4번 조건의 대각선을 2번 대각선 ( \ )이라고 정한다.
퀸 N 개가 배치될 위치를 찾기 위해, 먼저 퀸은 0번째 행부터 N - 1번째 행까지 차례대로 배치한다고 가정하고.
나머지 제약 조건인 (한 열에 한 개) (한 1번 대각선에 1개) (한 2번 대각선에 1개) 를 만족해야 한다.
좌표 체계를 자세히 관찰하면, 대각선 체계를 정할 수 있다.
각 칸마다 1번 대각선의 어디에 해당되는지를 구하고 싶다면 행 번호 + 열 번호를 하면 구할 수 있다.
각 칸마다 2번 대각선의 어디에 해당되는지를 구하고 싶다면 열 번호 - 행 번호를 하면 구할 수 있다.
2번 대각선은 음수가 나올 수 있으니 n 을 더해도 좋다.
다음과 같이 조건 체계를 정해, 해당 위치에 퀸을 배치할 때마다 column[x], diag_slash[y+x], diag_slash[x-y+n] 에 정보를 저장하여 다음 상태로 넘어가면서 완전해를 구할 때마다 카운트를 하면 결과를 구할 수 있다.
#include <stdio.h>
int n;
int count = 0;
int col[15] = {0,};
int diag_slash[30] = {0,};
int diag_rev_slash[30] = {0,};
void dfs(int c) {
if (c == n) {
count += 1;
return;
}
for (int i = 0; i < n; i++) {
if (col[i] == 0 && diag_slash[c+i] == 0 && diag_rev_slash[-c+i+n] == 0) {
col[i] = 1;
diag_slash[c+i] = 1;
diag_rev_slash[-c+i+n] = 1;
dfs(c + 1);
col[i] = 0;
diag_slash[c+i] = 0;
diag_rev_slash[-c+i+n] = 0;
}
}
}
int main(void) {
scanf("%d", &n);
dfs(0);
printf("%d", count);
return 0;
}
'-- 예전 기록 > Algorithm Tutorial' 카테고리의 다른 글
| [ Algorithm ] 재귀 (2) | 2023.06.30 |
|---|---|
| [ Algorithm ] 깊이 우선 탐색과 너비 우선 탐색 (4) | 2023.06.28 |
| [ Algorithm ] 큐 (0) | 2023.06.25 |
| [ Algorithm ] 느리게 갱신되는 세그먼트 트리 (0) | 2023.06.18 |
| [ Algorithm ] 세그먼트 트리 (0) | 2023.05.26 |