[알고리즘] 백트래킹

1 백트래킹

 백트래킹이란 조건을 가진 문제를 풀기 위한 전략이다. DFS와 재귀로 구현되며, 정답이 될 수 있는 후보의 탐색을 하면서 조건에 맞는다면 계속 탐색하고 맞지 않다면 그 후보를 배제하고 다음 후보의 탐색을 한다. 이러한 과정을 가지치기라고 하고 가지치기를 얼마나 잘 짜냐에 따라 백트래킹의 성능이 좌우된다.

2 예시

문제 링크: https://www.acmicpc.net/problem/15649 

15649번: N과 M (1)

 이 문제를 예시로 들겠다. 1부터 N까지의 자연수 중에서 중복 없이 M개를 골라 중복되지 않는 수열을 사전 순으로 출력하는 문제이다.

 

 문제를 푸는 방법은 1부터 N까지의 숫자중 하나를 고르고 고른 숫자를 제외한 1부터 N까지의 숫자 중에서 또 하나를 고른다. 이렇게 M개를 구할 때까지 하면된다. 여기서 이 문제에서 수열을 만들 때의 조건은 중복없이 숫자를 뽑는 것이다. N=4이고 M=3일 때를 살펴보겠다.

그림 1

 위에 그림 1을 보면 처음 시작하는 숫자로 1을 선택했다. 그 뒤의 숫자로 1부터 4까지 중에서 선택해야하는데 1의 경우에는 조건에 부합하지 않기 때문에 탐색을 중단하고 2로 선택하는 경우를 본다. 그 다음에 1부터 4까지 중에 1을 선택한다. 이러면은 만들 수 있는 수열 중 하나가 완성되었다. 이런 식으로 만들 수 있는 수열을 모두 만들 때까지 반복한다.

 

코드

#include <stdio.h>

int n, m;
int result[1000];
int check[1000];

void DFS(int depth)
{
    int i;

    if (depth == m)
    {
        for (int i = 0; i < m; i++)
            printf("%d ", result[i]);
        printf("\n");
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (check[i] == 0) // 뽑은 숫자가 중첩되지 않게 체크
            {
                result[depth] = i;
                check[i] = 1;
                DFS(depth + 1);
                check[i] = 0; // 만약 정답이 아니였다면 숫자를 뽑지 않았던 상태로 되돌아옴.
            }
        }
    }
}

int main(void)
{
    scanf("%d %d", &n, &m);
    DFS(0);
    return 0;
}

 참고로 사실 꼭 재귀를 이용하여 풀지 않아도 되긴한다. 근데 그럴 경우에는 for문을 많이 사용해야 해서 가독성이 좋지 않을 것이다.