[Algorithm] Back Tracking

백트래킹(Back Tracking)

---

백트래킹이란 해를 찾는 도중에 올바른 해가 아니면 전 상태로 되돌아가서 다시 해를 찾아가는 기법이다.

 

즉, DFS 와 같이 모든 경우의 수를 탐색하지만 중간에 올바르지 않은 해가 나올 경우 해당 가지를 가지치기해 하위 트리는 더 이상 확인하지 않는 것을 말한다. 이러한 가지치기는 불필요한 부분을 쳐내고 경우의 수를 최대한 줄여 최적화하가 가능합니다.

 

그렇기 때문에 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다. 즉, 시간이 단축된다는 말이다. 

 

언제 사용하면 좋을까?

---

백트래킹은 결국 모든 상황을 확인하는 전수 검사를 기반으로 하고 있기 때문에, 모든 상황에 대해서 직접 Brute Force 해야하는 경우 고려해볼 수 있다. 특히, 시간제한이 있거나 N이 작아 직접 확인해볼 수 있을 것 같은 상황에 백트래킹을 떠올릴 수 있을 것 같다.

 

또 전수 검사를 하는 과정에서 여러 가지 상황에 대해서 하나씩 맞는지 틀리는지 확인하고, 하나라도 틀리면 안된다면 백트래킹을 고려해볼 수 있을 것 같다.

 

하나라도 틀리면 다시 이전 상태로 돌아옴으로써 가지치기를 하는 형식이 될 것이다.

 

의사코드

---

def backtracking(cur):
	if "If at a Solution":
    		print(Currnet State)
        	return
   
	for i in "every possible choice from current state":
    		if "If not Promissing":
        		continue
        
        "change state"
        bactracking(cur + 1)
        "rollback state"

 

기본적인 의사코드는 다음과 같지만, 당연히 문제에 따라 변형이 가능하다. 여기서 중요한 포인트 몇가지를 살펴보겠다. 여기서 중요한 포인트라는 것은 변형될 때 반드시 신경써야하는 부분을 말한다.

 

1. backtracking 함수의 파라미터 cur

cur의 용도는 현재 상태가 올바른 해인지 판단하기 위한 기준으로 보통 사용된다. 다른 방법을 통해 현재 상태가 올바른 해인지 판단할 수 있다면 굳이 cur을 사용할 필요는 없다. 하지만, cur을 사용해 현재 상태가 올바른 해인지 판단하는 것은 매우 간단하고 직관적으로 작용할 수 있기 때문에 자주 사용될 수 있다.

 

2. "If at a Solution" 조건

현재 상태가 올바른 해인지 확인하는 방법에는 크게 2가지 방법을 들 수 있을 것 같다. (당연히 내가 아는 것 기준이기 때문에 더 많을 수 있다.) 1번 항목에서 언급한 cur을 이용해 cur이 특정 갯수(N)이 되었을 때가 올바른 해라고 판단하는 방법이 첫 번째 방법이다. 두 번째 방법으로는 isClear()와 같은 함수를 별도로 만들어 현재 상태가 올바른 해인지 판단하는 방법이 있다.

 

당연히 두 번째 방법이 정확하겠지만 올바른 해인지 직접 확인해야하는 과정이 필요하기 때문에 그에 따라 시간이 소요된다. 이는 속도 저하로 이어질 수 있다.

 

3. 반복문의 "every possible choice from current state"

현재 상태에서 변화하는 상태에 대해서, 해당 Node에 대해서 변화시킬 수 있는 모든 것을 말한다. 말이 조금 이상한데 예를 들면, 스도쿠의 경우 1~9가 될 수 있고, 체스게임의 경우 1~N이 될 수 있다. 

 

간단하게 설명하면 그냥 Node에 저장할 수 있는 모든 경우의 수를 반복문을 통해 확인하게 된다.

 

4. 반복문의 "If not Promissing" 조건

변화시킬 상태가 올바르지 않은 해인지 확인하는 조건문이다. 모든걸 완성해야 올바른 해인지 아닌지 알 수 있는 것이 아니라 중간 과정에서 올바르지 않은 해인지 확인하고 변화시킬 해가 올바르지 않은 해라면 이후 과정을 가지치기해 경우의 수를 최소화해 시간을 최소화하게 되는 것이다.

 

이 조건문이 DFS와 백트래킹의 차이라고 생각하면 좋을 것 같다.

 

이 조건문은 크게 두 가지 형태로 구성할 수 있는데, isPromise() 형태의 함수로 구성하는 것과 Boolean 형 배열을 이용하는 것이다. 마찬가지로 isPromise() 형태로 확인하는 것은 반복문등을 거치게 되기 때문에 그에 따른 시간복잡도 증가를 유발할 수 있다. 그러나 Boolean 형 배열을 이용한다면 O(1) 의 시간복잡도를 가지고 원하는 결과를 얻어낼 수 있다.

 

시간복잡도를 고려하면 Boolean 형 배열을 이용하는 방법을 선택하는 것이 좋지만, 올바른 해가 아닌지 확인하는 과정이 복잡하다면 함수를 사용하는 것도 직관적이고 좋은 방법이 될 수 있다.

 

5. "rollback state" 구문

변화시켰던 상태를 원상복구 시키는 구문이다. 그러나, 상태를 변화시킬 때 덮어쓰는 형태라면 이 구문은 생략해도 된다. 사실 해도되고 안해도되기 때문에 크게 중요한 부분은 아니긴하다.

 

 

실수할만한 포인트

---

위에서 소개한 의사코드에서 반복문 부분을 잘 살펴보자. 여기서 가능한 모든 것을 반복한다고 설명했는데, 일반적이지 않은 케이스에서는 이 부분을 유의해줘야 한다.

 

실수할만한 포인트는 바로 "중복 제거" 이다.

 

예를 들어, 스도쿠 같은 경우에는 모든 노드에 1이 올수도 있다. 그러나 팀원을 구성하는 것과 같이 중복에 대해서는 배제시켜도 되는 경우가 있다. 조금 구체적으로 설명하면, 스도쿠와 같이 중복이 발생해도 되는 경우에는 각 노드가 독립적인 경우이다. 그러나, 팀을 구성하는 경우 각 노드가 독립적이지 않고 하나의 팀으로 묶이기 때문에 [1, 2]나 [2, 1]이나 동일한 것이 된다.

 

그러면 이러한 부분에서 중복이 발생하는 것을 어떻게 방지할 수 있을까?

 

반복문의 시작 값을 설정하는 것이다. 아래 코드를 살펴보자.

def solution(cur):
    global N, start_links, isUsed
    global start_team, answer

    if cur == N // 2:
        link_team, link_sum, start_sum = [], 0, 0
        for i in range(N):
            if i not in start_team:
                for j in link_team:
                    link_sum += start_links[i][j] + start_links[j][i]
                link_team.append(i)
            else:
                for j in start_team:
                    if i >= j:
                        continue
                    start_sum += start_links[i][j] + start_links[j][i]

        answer = min(abs(start_sum - link_sum), answer)
        link_team.clear()
        return

    for i in range(len(start_links)):
        if isUsed[i]:
            continue

        start_team.append(i)
        isUsed[i] = True
        solution(cur + 1)
        start_team.pop()
        isUsed[i] = False


N = int(input())
start_links = []
for n in range(N):
    start_links.append(list(map(int, input().split())))
isUsed = [False] * len(start_links)

answer = 9999999999
start_team = []
solution(0)
print(answer)

 

반복문을 살펴보면 시작 값은 지정되어있지 않고 재귀할 때마다 모든 번호의 선수를 처리한다. 이렇게 구성할 경우 팀의 구성은 다음과 같이 될 수 있다.

 

start_team : [0, 1]   link_team : [2, 3]

start_team : [0, 2]   link_team : [1, 3]

start_team : [0, 3]   link_team : [1, 2]

start_team : [1, 0]   link_team : [2, 3]

start_team : [1, 2]   link_team : [0, 3]

start_team : [1, 3]   link_team : [0, 2]

start_team : [2, 0]   link_team : [1, 3]

start_team : [2, 1]   link_team : [0, 3]

start_team : [2, 3]   link_team : [0, 1]

start_team : [3, 0]   link_team : [1, 2]

start_team : [3, 1]   link_team : [0, 2]

start_team : [3, 2]   link_team : [0, 1]

 

보다시피 중복이 엄청나게 많이 발생한 것을 알 수 있다. [0, 1]와 [1, 0]을 다른 것이라 판단했기 때문이다. 이러한 문제를 해결하려만 다음과 같이 반복문의 시작 값을 지정해줘야 한다.

    for i in range(max(start_team) if start_team else 0, len(start_links)):
        if isUsed[i]:
            continue

        start_team.append(i)
        isUsed[i] = True
        solution(cur + 1)
        start_team.pop()
        isUsed[i] = False

 

이렇게 할 경우, 이미 지나온 수에 대해서는 더이상 고려하지 않기 때문에 오름차순으로 정렬된 것에 대해서만 백트래킹을 진행한다. 위의 경우에는 절반의 시간을 절약할 수 있고, 수가 커질수록 기하급수적으로 시간을 절약할 수 있게 된다.

 

이 문제는 백준 14889번 문제이다.

www.acmicpc.net/problem/14889

14889번: 스타트와 링크