[ 알고리즘 ] 7. 백트래킹 알고리즘

 

1. 백트래킹 알고리즘

- 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

- 해를 찾아가는 도중에 해가 안될 것 같으면 돌아간다.

 

ⓐ 유망하다 (Promising)

: 해가 될 가능성이 있다.

ⓑ 가지치기 (Pruning)

: 해가 될 가능성이 없다.

 

- 가지치기를 얼마나 잘 하는 지에 따라서 효율성이 결정된다. 

 

 

 

2. DFS와 백트래킹의 차이

(1) DFS (Depth First Search, 깊이 우선 탐색)

- 대표적인 완전 탐색 방법이다.

- 현재 지점에서 방문해야 할 곳이 있다면 재귀 호출을 이용해서 계속 이동한다.

 

ⓐ 장점

: 무한히 깊은 곳을 찾아야 할 때 효과적이다.

ⓑ 단점

: 모든 곳을 방문해야 하기 때문에 굳이 방문하지 않아도 되는 지점 (목표가 되지 않는 지점)을 거쳐야 하기 때문에 비효율적인 결과를 초래할 수도 있다.

 

(2) 백트래킹

- DFS의 종류 중 하나이다.

- DFS 과정에서 비효율적인 경로를 차단하고 목표 지점에 갈 수 있는 가능성이 있는 방법만 검사하는 방법이다.

- 가능성이 없는 루트를 가지치기로 쳐내서 탐색한다.

 

 

 

3. 백트래킹의 어려운 점

- 상당한 구현력을 요구한다.

- 재귀 호출이 잦아서, 틀리더라도 실수한 부분을 찾기가 쉽지 않다.

- 풀이는 알지만 코드로 옮기기가 어렵다.

 

 

 

4. 백트래킹 문제 유용한 툴 (tool)

- 상태 공간 트리 (State-Space Tree)

출처 : 바킹독

: 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리

 

 

 

5. 예제

BOJ 15649 : N과 M (1)

 

(1) DFS로 풀기

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

arr = []


def dfs():
    if len(arr) == m:
        print(' '.join(map(str, arr)))
    else:
        for i in range(1, n+1):
            if i not in arr:
                arr.append(i)
                dfs()
                arr.pop()


dfs()

- dfs 함수를 만들어서 깊이 우선 탐색으로 문제를 해결한다.

- 재귀적 호출을 반복하면서 arr의 길이가 m이 되었을 때 함수를 빠져나오고 마지막으로 들어온 값을 pop 하여 다른 원소를 검토하도록 한다.

 

 

(2) Back Tracking으로 풀기

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

arr = []

# 중복 선택되지 않아야 하므로 사용되었는지 구별해주는 리스트 사용. False : 미방문, True : 방문
isUsed = [False] * (n+1)
isUsed[0] = True


def backTracking():
  if len(arr) == m:
    print(' '.join(map(str, arr)))
  else:
    for i in range(1, n+1):
      if isUsed[i] == False:
        # i가 이미 선택되었기 때문에 True 값으로 바꿔준다. 그리고 arr에 i를 append한다.
        isUsed[i] = True
        arr.append(i)

        # 재귀 호출로 만약 arr 길이가 m과 같다면 출력하면서 재귀 호출을 멈추고, 그렇지 않다면 계속 append 하는 작업이 반복된다.
        backTracking()

        # 한 세트를 완성하고 나서는 i 값을 False로 바꿔준다. 그 후 가장 최근에 들어온 값을 pop 해준다.
        isUsed[i] = False
        arr.pop()


backTracking()

- isUsed 리스트를 만들어서 방문 했는지 안했는지 검토하는 작업을 진행했다.

 

 

(3) 비교

- 이 문제에서는 dfs에서 'not in'을 사용할 것인지, backtracking에서 'isUsed'를 사용할 것인지의 차이였다.

- 백트래킹 알고리즘 대부분은 (2)에서의 풀이처럼 isUsed 배열을 이용하는 풀이가 대부분이다. 그래서 DFS로 풀 수 있는 문제였지만, 백트래킹 알고리즘으로도 한번 풀어봤다.