백트래킹(Backtracking)

모든 경우의 수를 고려하는 알고리즘

깊이우선탐색(Depth First Search, DFS)
너비우선탐색(Breadth First Search, BFS)
최선 우선 탐색(Best First Search/Heuristic Search)
이 있다

이 중에서 DFS를 이용해서 백트래킹을 해볼 것이다

---

깊이 우선 탐색(DFS)

모든 노드를 방문하는데 그 중에서 깊이를 우선적으로 탐색하는 알고리즘
트리나 그래프에서 한쪽 방향으로 계속 탐색하다가 목표 노드에 도착하면, 이전 노드로 가서 탐색 반복

• 장점
  단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다
  목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다

• 단점
  해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다
  얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다

---

백준 19649 (N과 M (1))

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

이 문제를 백트래킹으로 풀었는데
n-queen 문제도 비슷한 코드로 풀 수 있다

---

코드

위 문제에서는 함수를 4개 사용했다
각각

• 메인 함수
• DFS 함수
• 목표 노드에 도달했는지 확인하는 함수
• 프린트하는 함수

#include <stdio.h>

void print_num(int *visit, int m)
{
    int i;

    i = 1;
    while (i <= m)
    {
        printf("%d", visit[i]);
        if (i != m)
            printf(" ");
        i++;
    }
    printf("\n");
}

int check(int *visit, int i)
{
    int j;

    j = 0;
    while (j < i)
    {
        //전의 값들과 비교해서 동일한 값이 있으면 false로
        if (visit[j] == visit[i])
        {
            return (0);
        }
        j++;
    }
    return (1);
}

void DFS(int *visit, int n, int m, int i)
{
    int j;

    if (i > m)
    {
        print_num(visit, m);
        return ;
    }
    j = 1;
    while (j <= n)
    {
        //backtracking
        visit[i] = j;
        if (check(visit, i))
            DFS(visit, n, m, i + 1);
        j++;
    }
}

int main()
{
    int visit[10] = {0};
    int n, m;

    scanf("%d %d", &n, &m);
    DFS(visit, n, m, 1);

    return (0);
}

---

참고

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9#s-1.1
https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89