백트래킹이란?

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법
• 최적화 문제와 결정 문제를 푸는 방법

전체 탐색을 하는 브루트포스 알고리즘의 DFS와 달리 백트래킹은 불필요한 탐색을 하지 않는다.

아래는 DFS와 백트래킹의 차이점을 보여주는 그림이다.

해당 그림 출처

위의 그림처럼 ALT라는 조합을 찾기 위해 DFS는 찾을 때까지 완전탐색으로 하나하나 찾는 반면, 백트래킹은 하나를 찾을 때 찾는 문자가 아닐 경우 되돌아가서 다시 해를 찾는다.

이를 코드로 구현하면 아래와 같다.

우선 차이점을 보여주기 위해 어떠한 단어 조합을 찾아보고자 한다.

단어 조합을 찾을 때 비교를 위해 A~Z까지 순서대로 찾고자 하였다.

차이를 명확하게 증명하기 위해 찾고자 하는 단어를 ZXYWVU (최악의 경우)로 지정하였다.

DFS

import sys
import time


def dfs(cnt, temp, visited):
    if cnt == len(target):
        if ''.join(temp) == target:
            print(temp)
            print(time.time() - start, 'sec')
            sys.exit()
        return
    for i, value in enumerate(graph):
        if visited[i]:
            continue
        temp.append(value)
        visited[i] = True

        dfs(cnt + 1, temp, visited)

        temp.pop()
        visited[i] = False


def solution():
    global graph, target, start
    input = sys.stdin.readline
    # target = ''.join([chr(x) for x in range(90,64,-1)])
    target = 'ZXYWVU'
    graph = [chr(x) for x in range(65, 91)]
    visited = [False for _ in range(65, 91)]
    start = time.time()
    dfs(1, [target[0]], visited)


solution()

• 결과
  

백트래킹

import sys
import time


def backtracking(temp, cnt):
    if temp[-1] != target[cnt]:
        return
    if ''.join(temp) == target:
        print(temp)
        print(time.time() - start, 'sec')
        sys.exit()
    for i in alphabet:
        temp.append(i)
        backtracking(temp, cnt + 1)
        temp.pop()


def solution():
    global target, alphabet, start
    input = sys.stdin.readline
    target = 'ZXYWV'
    alphabet = [chr(x) for x in range(65, 91)]
    start = time.time()
    backtracking(['Z'], 0)


solution()

• 결과
  

위의 결과들을 보듯이 백트래킹이 찾고자 하는 단어에 해당되지 않을 경우 전 경로를 되돌아 가는 방식임으로 시간이 DFS보다 많이 단축된 것을 볼 수 있다.