[알고리즘] 백트래킹 문제 - Sum of Subsets

백트래킹 문제 - Sum of Subsets

백트래킹(Backtracking)

백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻한다.

즉, 탐색하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 백트래킹이라는 이름이 붙었다.

 

 

출처: https://www.marioperez.me/2018/05/07/solving-the-peg-solitaire-with-backtracking.html

 

Sum of Subsets

백트래킹을 사용하여 해결할 수 있는 문제 중 Sum of Subsets이 있다.

Sum of Subsets은 집합 w의 부분집합 중 그 합이 숫자 K와 같은 부분 집합들을 찾는 문제다. 이때, 집합에 음의 값과 중복 값은 없다고 가정한다.

 

예제를 통해 문제를 이해해보자.

 

집합 w는 w₁ = 2, w₂ = 10,  w₃ = 13, w₄ = 17, w₅ = 22, w₆ = 42 이다. 

K = 52일때, K와 값이 같은 집합 w의 부분 집합들을 구해보자.

 

아래 트리에서 각 단계의 가지는 w₁ , w₂ ,  w₃ , w₄ , w₅ , w₆ 숫자를 의미한다. 루트 트리의 값 0부터 이동을 시작하여 연결된 가지에 해당하는 수를 더하거나(Y), 무시하고(N) 지나간다.

 

예를 들어 루트노드에서 왼쪽 경로(Y)로 가면 w₁ =2 값이 더해져 0+2 = 2의 값을 갖고, 오른쪽 경로(N)로 가면 값이 더해지지 않아 그대로 0의 값을 갖는다.

 

흰색 원은 각 가지들을 지나 더해진 숫자의 합이다. 흰색원 위에 작은 검정원은 트리의 이동 순서이다.

빨간 원은 경로의 합이 숫자 K를 넘어서 더는 경로를 탐색할 필요가 없어졌거나, 모든 자식 노드를 탐색했지만 합이 K가 아니었음을 의미한다. 이때는 길을 되돌아(Backtraking)간다. 이것을 `가지치기`라고 한다. 

초록 원은 경로의 합이 K값으로, 탐색에 성공한 것을 의미한다.

 

루트노드부터 출발해보자.

 

1번(순서는 검정색 원에 적혀있다)으로 이동하여 현재 값은 2다. 

2번으로 이동하여 현재 값은 12다.

3번으로 이동하여 현재 값은 25다.

4번으로 이동하여 현재 값은 42다.

5번으로 이동하여 현재 값은 64다. K 값인 52보다 크다. 되돌아간다.

6번으로 이동하여 현재 값은 42다.

7번으로 이동하여 현재 값은 84다. K 값인 52보다 크다. 되돌아간다.

8번으로 이동하여 현재 값은 92다. K 값인 52보다 크다. 되돌아간다.

9번으로 이동하여 현재 값은 25다.

10번으로 이동하여 현재 값은 47이다.

11번으로 이동하여 현재 값은 92다. K 값인 52보다 크다. 되돌아간다.

12번으로 이동하여 현재 값은 47다. 더 이동할 자식 노드가 없으며, K 값인 52 보다 작다. 되돌아간다.

13번으로 이동하여 현재 값은 25다.

14번으로 이동하여 현재 값은 67이다. K 값인 52보다 크다. 되돌아간다.

15번으로 이동하여 현재 값은 25다. 더 이동할 자식 노드가 없으며, K 값인 52 보다 작다. 되돌아간다.

16번으로 이동하여 현재 값은 12다.

 

더 탐색할 노드가 없을 때까지 이 행위를 반복하며, K값과 그 합이 같은 집합 w의 부분 집합을 찾으면 된다.

 

위 예제를 c 언어로 구현하면 아래와 같다.

#include <stdio.h>
#define size 6

int K = 52; // 목표한 숫자
int w[size] = {2, 10, 13, 17, 22, 42};
char include[size]; // w 집합의 원소 중 경로에 포함되는 지 표시('y' or 'n')
void printSubset(){
    for(int i = 0; i < size; i++)
        if(include[i]!='n')
            printf("%d ",w[i]);
    printf("\n");
}

// 검사할 노드의 하위 노드로 검색할 계속할 지 결정하는 함수
int promising (int i, int weight, int total){
    return (weight+total >= K) && (weight == K || weight+w[i+1] <= K);
}

/* sum_of_subsets 알고리즘을 수행하는 함수
*	i: 집합 w의 인덱스
*	weight: 이동한 가지들의 가중치를 더한다 
*	total: 가지치기에 활용하기위해 집합 w의 모든 원소의 합을 저장
*/
void sum_of_subsets(int i, int weight, int total){
    if(promising(i, weight, total)){
        if(weight == K){
            printSubset();
        }else{
            include[i+1] = 'y';
            sum_of_subsets(i+1, weight+w[i+1], total-w[i+1]);
            include[i+1] = 'n';
            sum_of_subsets(i+1, weight, total-w[i+1]);
        }
    }
}


int main(int argc, const char * argv[]) {
    
    //알고리즘 연산을 위해 필요한 값 초기화
    int total = 0; // total: w 집합 모든 수의 합
    for(int i=0; i<size; i++){
        total += w[i];
        include[i] = 'n';
    }
    
    sum_of_subsets(-1, 0, total);
      
    return 0;
}

 

결과

10 42 

13 17 22