백트래킹(Backtracking) 나만의 정리

백트래킹(Backtracking)

• 여러가지 선택지들이 존재하는 상황에서 한가지를 선택한다.

• 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.

• 이런 선택을 반복하면서 최종상태에 도달한다.

  • 올바른 선택을 계속하면 목표상태(goal state)에 도달한다.

1. 백트래킹 개념

• 모든후보를 검사??
  • Nope!!
• 백트래킹 기법
  • 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식노드로 감
  • 어떤 노드를 방문하였을때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망한다고 한다.
  • 가치지기(pruning) : 유망하지 않는 노드가 포함된 경로는 더 이상 고려하지 않는다.

2. 백트래킹과 깊이 우선 탐색(dfs)과의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임(Prunning 가지치기)
• 깊이우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단
• 깊이우선 탐색을 가하기에는 경우의 수가 너무나 많음. 즉! N! 가지의 경우의 수를 가진 문제에 대해 깊이우선 탐색을 가하면 당연히 처리 불가능한 문제
• 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 Exponential Time을 요하므로 처리 불가능

차이점 정리

1. dfs는 그래프에 대해서 하는거 (dfs는 모든 정점을 한번씩 방문하기위한 목적)
2. 백트래킹은 dfs와 코드 구현은 비슷하지만 그래프에 대해 다루진 않는다.
   (백트래킹은 모두 방문보다는 불필요한 경로를 조기에 차단 == 가지치기(prunning))

3. 백트래킹을 이용한 알고리즘의 절차

1. 상태 공간 트리의 깊이 우선 검색(DFS)을 실시한다.
2. 각 노드가 유망한지를 점검한다.
3. 해당 노드가 유망하지 않다면 부모로 돌아가서 검색을 계속한다.

4. 대표적인 예

(1) 8-queen 문제

def backtrack(idx): # idx = 행
    global n,cnt
    ###############################목표###################################
    if idx == n:                        # 목표달성
        # idx = 행과 같다 ==> 해를 다 찾음
        cnt +=1
        return
    ###############################promising#############################
    # 해당 상태에서 선택할 수 있는 후보군 생성
    # 노드가 유망한지 확인 : 유망한 열 ,,
    for j in range(n):  # j 는 열을 의미, idx는 행
        # if 열이 유망하고, 상향대각, 하향대각들이 유망(사용하지 않아야함)
        if not col[j] and not dia_1[idx+j] and not dia_2[n+j-idx-1]:    # 가지치기
            # 유망하다면 해당 위치의 열,대각선2개를 방문표시한다
            # 모든 후보군들에 대해 다음상태 실행
            col[j] =1
            dia_1[idx + j] =1
            dia_2[n + j - idx - 1] =1
            # 방문표시 한뒤 다음선택 진행
            backtrack(idx+1)    # 해당 자손들을 모두 탐색한뒤 다음 형제로 가기위해 열, 대각들을 0으로 재정의
            col[j] =0
            dia_1[idx + j] =0
            dia_2[n + j - idx - 1] =0

T = int(input())
for tc in range(1,T+1):
    n = int(input())
    # 각행에는 1개의 퀸만 올수있음
    col = [0]* n    # 열의 사용 여부
    # 대각 유명성을 판단할 리스트
    # 대각의 갯수파악 : 2 * n - 1
    # 상향 대각(왼밑 -> 오른위) : 특징 idx,j의 합이 같음
    dia_1 = [0] * (2 * n - 1) # i+j
    # 하향 대각(왼위 -> 오른아래) : 특징 idx와 k의 차가 일정
    dia_2 = [0]*(2 * n - 1) # n+j-i-1
    cnt = 0
    backtrack(0)
    print("#{} {}".format(tc,cnt))

(2) 백트래킹을 이용한 부분집합

# [1,2,3,4,5,6,7,8,9,10]의 powerset중 원소의 합이 10인 부분집합을 모두 출력하라
def subset(k,sum_num):
    global cnt
    cnt +=1
    if sum_num > 10:    # 가지치기
        return
    if k == n:          # 목표도달
        if sum_num == 10:
            for i in range(n):
                if visited[i]:
                    print(arr[i], end=" ")
            print()
        return

    else:
        visited[k] = 1
        subset(k+1,sum_num+arr[k])
        visited[k] = 0
        subset(k+1,sum_num)
arr = [1,2,3,4,5,6,7,8,9,10]
n = len(arr)
cnt = 0
visited = [0]* n
subset(0,0)

(3) 백트래킹을 이용한 순열구하기

• 접근 방법은 부분집합 구하는방법과 유사

# 백트래킹을 이용한 순열구현
def backtrack(result, visited,k,n):
    if k == n:
        print(result)
        return
    # 사용 가능한 선택지 후보군에 대하여 다음단계로 진행
    for i in range(n):
        if not visited[i]:         # 선택되지 않았다면
            visited[i] = 1
            result[k] = i     # result의 idx에 i저장
            backtrack(result, visited, k+1, n)
            visited[i] = 0
n = 5
backtrack([0]*n,[0]*n,0,n)

백트래킹 나만의 정리

아주 복잡해보이지만 문제푸는법은 아주 간단하다

1. 완전검색을 하여 모든 경우의수를 검색가능한 알고리즘 구성
2. promising을 확인하여 가지치기하자!! ==> 시간 및 메모리 단축

백트래킹을 이용한 순열, 부분집합 등 다양한 알고리즘을 구현가능하고, 문제를 풀기위해서 이러한 개념들은 반드시 잡고가자!!