백트래킹

백트래킹 기법

백트래킹은 해를 찾는 도중에 ‘막히면’ (즉, 해가 아니라면) 되돌아가서 다시 해를 찾는 기법이다.

 

모든 경우를 다 탐색하는것이 아니라 해가 아니라면 되돌아가기 때문에 최적화 문제와 결정 문제를 해결하는데 사용될 수 있다.

 

여기서 결정 문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 ‘yes’ 또는 ‘no’로 답하는 문제를 말한다. 대표적인 결정 문제로 n-queen, map coloring, 부분 집합의 합 등이 있다.

 

또한 최적화 문제에는 미로찾기(출구까지 최단경로를 찾는), 부분집합의 합중 원소의 개수가 최대인 부분집합을 찾는 문제 등이 속한다.

 

백트래킹의 대략적인 흐름은 다음과 같다.

• 여러가지 선택지들이 존재하는 상황에서 한가지를 선택한다.
• 선택이 이루어지면 그 선택에 따른 새로운 선택지들의 집합이 생성된다.
• 이런 선택을 반복하면서 최종상태에 도달하게 된다. 이때 올바른 선택을 계속하면 목표상태에 도달 할 수 있다.

---

트리의 루트부터 당첨 단말 노드를 찾는 예시로 백트래킹이 어떻게 동작하는지 살펴보자.

 

 

이 경우 어떤 경로를 선택해야 당첨 단말노드까지 갈 수 있는지는 알 수 없다.

 

때문에 당첨 노드까지 가기위해서 모든 경로에 대해서 탐색하여야 한다.

1. 루트에서 갈 수 있는 노드를 선택한다. 여기선 A와 B가 보인다. 먼저 A노드를 선택해보자.
2. 이어 C노드를 선택하고 C노드는 꽝임을 알 수 있다.
3. 원하는 해가 아니므로 다시 A노드로 돌아가서 D노드를 선택한다.
4. D노드 또한 꽝임으로 A노드로 돌아가고 A노드에서 더이상 갈 수 있는 노드가 없음으로 루트로 돌아간다.
5. 또다시 B노드를 선택한후 위 과정을 반복해서 당첨 단말 노드를 찾는다!

 만약 모든 노드를 탐색한후 루트로 돌아갔다면 그것은 해가 없다는 뜻이다!

---

DFS vs 백트래킹

위 그림을 보면 모든 경로를 탐색하는 DFS와 동일해 보일 수 있다.

 

그래서 DFS와 백트래킹은 시작 경로에서 탐색을 시작해 해를 구한다는 점에서 공통점이 있다. 그래서 주어진 상태 공간 트리에 DFS를 시작한다.

 

하지만 백트래킹은 가지치기를 해서 불필요한 경로탐색을 조기에 차단해 시도횟수를 줄인다는 점에서 DFS와는 다르다.

 

가지치기는 해당 노드가 유망한지를 판단하여 만약 그렇지 않다면 해당 노드가 포함된 경로는 더 이상 고려하지 않음을 의미한다. 그래서 유망하지 않은 노드는 해당 노드의 부모로 다시 돌아가 다음 자식노드로 탐색을 시작하게 된다.

 

---

백트래킹 알고리즘

def checknode(v): # 노드
	if promising(v): # 유망한 노드인가 체크(유망하다면 재귀호출 하지 않고 종료)
		if there is a solution at v:
			return
	else: 
		for u in each child of v:      #유망하지 않다면 재귀호출한다.
			checknode(u)

 

백트래킹 문제

백준의 n과 m문제들은 시리즈별로 있기에 풀어보면 백트래킹에 익숙해 질 수 있을 것이다.

https://www.acmicpc.net/problem/15649

 

N과 M(1)문제

N과 M문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 고르는 문제이다.

n, m = map(int, input().split())

# 수열을 담는 리스트
arr = [0] * 10

# 사용된 숫자인지 체크하는 리스트
isused = [False] * 10

# k를 증가시키면서(자리수를 증가) 마지막 수열일때 수열을 담은 리스트에서 프린트한다. 
def func(k):

    if m == k:
        for num in range(m):
            print(arr[num], end=' ')
        print()
        return

    # 1부터 n까지 수열을 만든다
    for i in range(1, n+1):

        # 만약 i가 사용되지 않았다면 수열 리스트에 담고 사용됐으니 isused에 담는다!
        if not isused[i]:
            arr[k] = i
            isused[i] = True
            func(k+1)

            # 말단 노드를 다 만들고 다시 올라오는 로직()
            isused[i] = False

func(0)
# 입력
# 4 2
# 출력
# 1 2
# 1 3
# 1 4
# 2 1
# 2 3
# 2 4
# 3 1
# 3 2
# 3 4
# 4 1
# 4 2
# 4 3

• for 루프로 만들어지는 숫자들을 isused를 사용해서 유망성을 체크
• 만약 유망하다면(쓰이지 않았다면), 수열을 만드는 배열에 집어넣고 아닌 경우 다음으로 넘어간다.
• 만약 수열을 다 만들었을 때, 즉 m과 자리수를 나타내는 k가 같을 때 수열 리스트를 돌면서 출력한다.