[알고리즘] 백트래킹(Backtracking)에 대해 알아보기

Backtracking

1. 노드를 이동하며 해를 탐색합니다.
2. 해가 아니라면 이 노드 및 서브트리를 가지치기합니다.
3. 이전 단계의 노드로 돌아옵니다.

이때, 1에서의 탐색 방법에 따라 다음과 같이 나눌 수 있습니다.

• DFS(Depth First Search, 깊이 우선 탐색)
• BFS(Breath First Search, 너비 우선 탐색)

사진으로 나타내면 다음과 같습니다.

DFS

한 방향으로 탐색을 하다가, 해를 찾지 못하면 이전 단계의 분기점으로 돌아와서 다른 방향을 탐색합니다. 해를 찾기 위해 탐색하다보면 결국 자식 노드를 우선적으로 탐색하기 때문에 이 알고리즘을 Depth First Search(깊이 우선 탐색)이라고 부릅니다.
특징은 다음과 같습니다.

• 모든 노드를 방문할 수 있습니다.
• 재귀를 사용할 수 있습니다.
• 해를 못찾아도 막다른 벽에 도달할때까지 깊이가 깊어지며 탐색하기 때문에 검색속도가 BFS보다 느립니다.
• 자료구조로 스택을 사용합니다

BFS

시작 노드를 정한 뒤 인접한 노드들을 모두 탐색하고, 해를 찾지 못하면 그 다음으로 인접한 노드를 탐색합니다. 단, 인접한 노드라고 해도 기존에 탐색을 시작했던 노드와는 거리가 멀 것입니다. 탐색하다보면 자식 노드보다는 형제 노드 또는 깊이가 동일한 노드를 먼저 탐색하는 경향이 있기 때문에 이 알고리즘을 Breath First Search(너비 우선 탐색)이라고 부릅니다.
특징은 다음과 같습니다.

• 재귀를 사용할 수 없습니다.
• 두 노드 사이의 최단 경로 및 임의의 경로를 찾을 수 있습니다. Prim, Dijkstra 알고리즘과 유사합니다.
• 자료구조로 큐를 사용합니다.

DFS, BFS 의사 코드, 실제 코드 구현해보기

---

백준 15649번 - N과 M(1)

https://www.acmicpc.net/problem/15649

DFS 문제입니다. 해가 아니라면 return해서 이전 분기점으로 나오는 백트래킹이 핵심입니다.

#include <stdio.h>
int M, N;
int Arr[8], V[8] = {0};

void BT(int C){
    if(C == M){
        for(int i = 0; i < M; i++){
            printf("%d ", Arr[i]);
        }
        printf("\n");
        return;
    }
    for(int i = 0; i < N; i++){
        if(V[i]) continue;
        V[i] = 1;
        Arr[C] = i + 1;
        BT(C + 1);
        V[i] = 0;
    }
    return;
}

int main(){
    scanf("%d %d", &N, &M);
    BT(0);
}