[C/C++] 백트래킹 알고리즘

백트래킹이란 ?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하다가, 가능성이 없다고 판단되면 가장 최근에 방문했던 노드로 다시 돌아감.

 

백트래킹을 푸는 과정

상태 정의 : 문제의 각 단계에서 가능한 상태를 정의

유망함수(IsPromising) : 현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색하지 않음.

해결책 확인(IsSolution) : 현재 상태가 문제의 해결책인지 판단

재귀 호출 : 유망한 상태 판단을 위해 사용

위의 과정을 기본적으로 코드로 구현하면 아래와 같다.

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################

// 유망성 판단 함수
bool isPromising(int level, State state) {
    // 현재 상태가 유망한지 판단하는 로직을 구현합니다.
}

// 해결책 확인 함수
bool isSolution(State state) {
    // 현재 상태가 문제의 해결책인지 판단하는 로직을 구현합니다.
}

// 백트래킹 함수
void backtrack(int level, State state) 
{
    // 현재 상태가 해결책이면 처리
    if (isSolution(state)) {
        processSolution(state);
        return;
    }
    // 다음 가능한 상태를 탐색
    for (State nextState : possibleStates(state)) //모든 경우에 대해서
    {
        if (isPromising(level, nextState)) //유망하면
        {
            backtrack(level + 1, nextState);//다음 상태를 백트래킹
        }
    }
}

 

백트래킹 예시 ( 부분 합 )

백트래킹 예시 ( 부분 합 )

 Q. {1,2,3,4}로 이루어진 집합에서 숫자를 뽑아서 합이 5인 조합 구하기

출처 https://www.slideshare.net/slideshow/c-12/269972942

뽑은 숫자의 합이 5가 되면 더 이상 탐색할 필요가 없음(IsSolution == true) 

해당 숫자를 조합하여 목표 값을 초과하면 유망하지 않다고 판단 (IsPromising == true) 

ex) {1,2,3} 뽑은 숫자 조합의 합은 6 다음 숫자가 4이므로 이미 목표 값(5)가 넘었으므로 더이상 유망하지 않다고 판단.

 

---

참조 

https://www.slideshare.net/slideshow/c-12/269972942

https://youtu.be/VvcEx75Bgvk?si=TrzrYsS9sRsiosz0