알면 좋은 쉬운 알고리즘 Back Tracking

목차

1. Back Tracking의 개념/이해

2. Back Tracking 활용 방향

3. 다양한 Back Track 구현

 

Back Tracking의 개념/이해

Back Tracking은 최적 값을 찾는데 사용할 수 있는, 글쓴이의 개인적인 의견으로는 제일 쉬운 방법입니다. Back Tracking은 말 그대로 값을 뒤로 추적하는 방법입니다. 기본적인 원리는 DFS를 기반으로 탐색을 진행하고 아니다! 싶으면 다시 돌아가는 방법이자 하나의 기법이라고 생각하면 됩니다. 일반적으로 재귀로 구현하는 것이 정석이고, 그 외의 방법으로 구현하는 것은 아직까지는 보지 못했습니다.

 

Back Tracking을 쉽게 생각하자면 우리가 수학문제 푸는 것과 비슷하다고 생각하시면 됩니다.

우리가 수학문제를 처음 풀 때, 일단 풀이를 쭉 해 나갑니다. 그런데 만약 답이 아니라는 것을 알게 된다면 틀린 부분을 지우고 다시 풀어 답을 맞추는 형식으로 풀어갑니다.

 

이처럼 Back Tracking도 일단 진행을 한 다음에 답이 아니라고 판단이 되면 더 이상 진행하지 않고 반대로 돌아간 다음에 돌아간 지점부터 다시 진행을 시킵니다.

 

Back Tracking 활용 방향

Back Tracking은 다양한 방향으로 활용이 가능합니다. 위에 언급했던 것처럼 최적 값을 찾는데에 사용할 수도 있지만, 가중치 그래프에서 최소 비용을 구할 때도 사용할 수 있고, 조건문을 조금 처리해 주면 최적값이 몇개인지도 찾을 수 있습니다.

 

다양한 Back Tracking 구현

1. 최적값을 찾는 방법 ( 문제 : https://codeup.kr/problem.php?id=3510 )

 연산을 진행하고 조건에 대해 판별을 합니다. 그런 다음 재귀를 진행시키고 Back Track 해서 돌아오면 시도해 보지 않은 다른 경우로 진행해 나갑니다. 예시 코드는 다음과 같습니다.

int k, n, ck, a[30];

void solve(int p, int sum) {
    if(p == n+1 || sum > k) return;
    sum += a[p];
    if(ck <= sum && sum <= k) ck = sum; // 찾는 답의 조건에 부합하면 저장
    solve(p+1, sum); // 다음 값으로 이동
    solve(p+1, sum-a[p]); // Back Track 해서 돌아오면 진행했던 값을 제거하고 다음 값으로 이동
}

이걸 그래프로 표현하면 다음과 같이 표현할 수 있습니다.

전체적인 진행 방식을 표현한 그래프

필요한 부분만 표현한 그래프

조금의 설명을 붙여보자면, 우선 첫번째 데이터를 더합니다. 그 다음 두번째 데이터도 더합니다. 그리고 3번째 데이터를 더했을 때 이 이상은 답이 될 수 없으므로 3번째 데이터를 제거한 다음에 그 다음 노드로 넘어갑니다. 그 다음부터는 데이터를 더하면 총 가격을 넘어버리므로 연산하지 않습니다.

 

2. 가중치 그래프 최소 비용을 찾는 방법 ( 문제 : https://codeup.kr/problem.php?id=4454 )

 여기서의 Back Tracking은 조금더 이해하기 쉬울 수도 있습니다. ( 꽤나 직관적이기 때문이죠~! )

연결된 정점을 방문하면서 그래프를 탐색을 해 줄건데, 만약 이미 갔었던 지점이라면? 탐색할 필요가 없으니 제외시키고, 가지 않은 지점이라면 체크해주고 해당 지점으로 이동합니다. 여기서 Back Tracking 이 쓰이는데, 만약 돌아왔다면? 체크를 풀어주고 탐색을 진행합니다. 예시 코드는 다음과 같습니다.

int v, a, b, e, d[110][110], M = INT_MAX, ck[110];

void solve(int V, int W) {
    if(W > M) return;
    if(V == b) {
        if(W < M) M = W;
        return;
    }

    for(int i=1; i<=v; i++)
        if(d[V][i] && !ck[i]) {
            ck[i] = 1;
            solve(i, W + d[V][i]);
            ck[i] = 0;
        }
}

int main()
{
	f(a, 0);
	...
}

 

-- 좀 더 표현하기 쉬운 그래프 구상 중...( 그리는 데로 바로 올려드림! )

 

위 두 예시 외에도 그래프로 표현한 다음에  Back Tracking을 이용하면 최적값을 쉽게 찾을 수 있습니다. 다만 탐색을 배제하더라도 너무 큰 값이 입력되면 악마의 체점데이터에서 탐색하다가 TLE가 날 수도 있다는 것을 꼭 알고 계셨으면 좋겠습니다.

 

이상으로 글을 마치겠습니다. 의문이 들거나 설명이 필요한 부분은 댓글로 남겨주시면 답변해 들리겠습니다. 감사합니다!