[Algorithm] 재귀(recursion)의 응용 - 서바이벌 문제

💡 위 이미지의 숫자와 같이, A~G까지 각 국가는 각자 위와 같은 힘을 가지고 있다. 혼자 있는 것보다 합치는 것이 유리하므로, 각 국가는 동맹을 맺기 시작하였고, 결국 두 축(axis)을 중심으로 힘의 균형을 가지게 되었다. 이 경우 어떤 조합으로 동맹이 될 때, 두 축의 힘의 차이가 최소를 이루게 될까?

위 문제는 Union Find의 문제와 유사하지만, backtracking을 통해서도 구현할 수 있는 문제이다. Union Find에서는 하나의 최종보스를 공유하여, 그를 중심으로 뭉치는 아이디어라면, backtracking에서는 1팀, 2팀을 애초에 정하여 A~F의 경로별로 팀 번호를 부여해주는 식의 아이디어를 사용한다

각 Branch에서 A,B를 선택할 수 있는 모두 경로에 대해, A팀과 B팀 사이의 최소 값을 갱신한다. 재귀의 경우에는 무엇을 branch로, 무엇을 Level로 볼 것인지가 중요한데, 이 문제에서는 branch를 'A,B팀의 종류'로 Level을 '각 팀의 선택'으로 보았다.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
string name = "ABCDEFG";
int power[7] = { 50,40,99,5,25,6,37 };
int minGap = 21e8;
char path[10];
void run(int level, int sumA, int sumB) {

    if (level == 7) { 
        int gap = abs(sumA - sumB); //A와 B팀의 차이를 min값 갱신
        if (minGap > gap) {
            minGap = gap;
        }
        return;
    }
    //첫 번째 Branch에서는 A팀으로
    path[level] = 'A';
    run(level + 1, sumA + power[level], sumB);
    //두 번째 Branch에서는 B팀으로 
    path[level] = 'B';
    run(level + 1, sumA, sumB + power[level]);

}

int main()
{
    run(0, 0, 0); // 1) level, A팀 합, B팀 합을 시작점으로
    cout << minGap;
    return 0;
}