[Algorithm] 백트래킹(+순열, 조합) 이론 + 구현

❗BackTracking

탐색 알고리즘 중 하나로 가능한 후보 해를 탐색하여 문제를 해결하는 방법이다.
 
 

❗동작 방식

1. 해를 구성하는 과정에서 해가 유망한지 확인
유망하지 않은 경우 현재 경로를 포기하고 다른 경로로 이동한다.
여기서 유망의 기준은 '현재 선택된 경로가 문제의 해답을 구하는 데에 있어서 가능성이 있다'는 의미이다.
2. 유망한 경우, 해가 완전한지 확인
완전한 해인 경우 해답을 출력하거나 저장한다.
완전하지 않은 경우 다음 단계로 나아가 계속 해를 확장한다.
 
 

❗파이썬 구현

백트래킹 구현의 가장 대표적인 예시로 순열과 조합을 들 수 있다.
이 두 알고리즘을 백트래킹으로 구현하기 위해선 뽑은 숫자를 저장한 arr 리스트, 방문 여부 파악을 위한 visited 리스트가 필요하며 백트래킹 함수 내부에선 해당 지점을 방문 처리 후 재귀 함수를 호출했다가 이 함수가 종료된다면 해당 지점을 다시 방문하지 않음으로 처리하여 다음 단계에서 사용할 수 있도록 해 줄 수 있다.
 
1️⃣ 순열(permutation)

import sys
import copy

input = sys.stdin.readline

answer = []
num = [2, 5, 6, 3, 9]
num.sort()

visited = [0 for _ in range(5)]

# 선택된 숫자를 저장할 리스트
arr = [0 for _ in range(2)]

def backTraking(dep):
	# dep가 뽑고 싶은 개수가 될 때까지
    if dep == 2:
        # print("dep: ", dep, " arr: ", arr)
        temp = copy.deepcopy(arr)
        answer.append(temp)
        return

    for i in range(len(num)):
        if not visited[i]:
            arr[dep] = num[i]
            visited[i] = 1
            backTraking(dep+1)
            visited[i] = 0

backTraking(0)

for a in answer:
    print(*a)

 
2️⃣ 조합(combination)

import sys
import copy

input = sys.stdin.readline

num = [1,2,3,5,8,13,21,34]
num.sort()
n = len(num)

visited = [0 for _ in range(n+1)] 
arr = [0 for _ in range(6)] # 선택된 숫자를 저장할 리스트
answer = []


def backTrack(num, dep, pre):
    # 뽑을 개수 dep
    if dep == 6:
        temp = copy.deepcopy(arr)
        answer.append(temp)
        # print("dep: ", dep, " arr: ", arr)
        return

    for i in range(pre, len(num)):
        # 이전 인덱스부터 시작해야 뒷 부분에서의 순열을 구할 수 있음
        if not visited[i]:
            # 현재 뎁스에 i번째 num 넣기
            arr[dep] = num[i]
            visited[i] = 1
            backTrack(num, dep + 1, i)
            visited[i] = 0

backTrack(num, 0, 0)

for a in answer:
    print(*a)

 
 

❗DFS와의 차이점

재귀를 사용하고 depth를 따라 깊게 탐색한다는 점에서 두 알고리즘은 비슷하지만 약간의 차이점이 있다.

DFS	BackTracking
모든 경로를 끝까지 탐색	유망하지 않은 경로는 조기 차단
그래프 탐색, 경로 찾기 등 일반적인 탐색 문제	최적화 문제, 조합 문제 등 가능한 해를 찾는 문제
모든 경로를 탐색하는 문제라 효율적이지 않을 수 있음	유망하지 않은 경로를 차단하여 탐색 공간을 줄임

 
 

❗참고 문제

https://www.acmicpc.net/problem/15649
https://radiant515.tistory.com/556

[Baekjoon] 백준 2644 로또

https://radiant515.tistory.com/614

[Baekjoon] 백준 1941 소문난 칠공주 Python