[개념] Backtracking(되추적 기법)

백트래킹(Backtracking)은 깊이우선검색(DFS)을 기반으로 하는 알고리즘 기법으로, 가능한 모든 경우를 탐색하되 유망하지 않은 경로는 즉시 포기하고 이전 단계로 돌아가는 방식입니다. 이 글에서는 백트래킹의 개념과 4-Queens Problem, Sum-of-Subsets Problem(부분합), Graph Coloring(그래프 색칠), Hamiltonian Circuits(해밀토니안 회로) 등 대표적인 응용 사례를 설명합니다.

백트래킹과 분기한정법을 같이 알아두면 좋다.

백트래킹은 깊이우선검색(DFS)을 기반으로 하지만, 분기한정법은 여러 검색 방법들을 지원하는 차이가 있다.

여기선 백트래킹을 알아보도록 하자.

Backtracking(되추적)

깊이우선검색을 기반으로 검색을 진행하며, 각 마디가 유망하지 않으면 그 마디의 부모 마디로 돌아가서 다시 검색을 계속하는 방식이다.

• 깊이우선검색 = 전위트리순회(preorder tree traversal)
  • root부터 자식들을 왼쪽->오른쪽 으로 순회
  • 순수한 깊이우선검색은 당연히 되추적이 없으며, 언어 혼동하지 말 것.

• 상태공간트리(State Space Tree) : 모든 가능한 경우의 수를 나타낸 트리

• 동작방식

  1) 상태공간트리의 깊이우선검색을 실시

  2) 각 마디가 유망한지 점검(promising)

  3) 만약 유망하지 않으면, 그 마디의 부모 마디로 돌아가서 검색을 계속

4-Queens Problem

4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스판에 위치시키는 문제이다.
서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선 상에 위치하지 않아야한다.

• 무작정 알고리즘(브루트포스)의 경우 모든 경우의 수(복잡도)는 4*4*4*4=256 이란건 4x4 체스판이므로 쉽게 이해가 될 것이다.
• 그런데, 되추적기법을 사용한다면?? 얼마나 효과적으로 경우의 수가 줄어들까??
  • 실제로 브루트포스 방식으로 상태공간트리를 그려보면 155 마디이고,
  • 되추적은 27 마디만에 첫 해답을 찾을 수 있다.
• 아래에서 상태공간트리와 코드형태를 확인하자.

Sum-of-Subsets Problem(부분합)

어떤 정수의 집합 S={1,2,4,5… 등}, 어떤 정수 W=30 이런식으로 주어졌을때, S의 부분집합의 합이 W가 되는 모든경우를 구하는 것이 이 문제의 요구사항이다.

• 상태공간트리가 선택은 1, 선택X는 0으로 구분
• 주어진 값보다 크면 Backtrack
• 역순 정렬 및 누적 합 이용하면 더 빠른 Backtrack
  • 따라서 이 방식으로 구하는 과정을 소개하겠다.

• 참고로 트리를 보면 오른쪽 하위는 1과 0중 0을 의미(S의 요소를 안더한다는 것)
• 또한, 왼쪽 하위는 1과 0중 1을 의미(S의 요소를 더한다는 것)
• S집합을 역순으로 정렬하고, 따로 누적합을 미리 계산해둔다
  • 누적합은 아래에서부터 차례로 합해서 구해두면 된다.
  • 이를 구하는 이유는 그림처럼 처음 66에선 누적합 13을 더하면 71(W)보다 크니까 더 깊이 내려가는 판단을 함.
  • 그리고 아래에 75는 이미 71(W)보다 커서 탈락.
  • 아래에 66은 누적합 4를 더해도 71(W)보다 작아서 탈락.
    • 이부분 때문에 누적합을 이용하면 좀 더 성능을 향상시킬수 있다.
• 정답이 가능한 모든경우를 구하는거기 때문에 위 방식을 통해서 끝까지 확인해서 최종 해들을 구함.

Graph Coloring(그래프 색칠 = 지도 색칠)

그래프의 정점을 m가지 색으로 색칠 및 인접 정점은 서로 다른 색으로 색칠하는 문제이다.

• 평면그래프(Planar Graph) : 에지들이 엇갈리지 않게 그린 or 그리기 가능한 그래프
• 플레인그래프(Plane Graph) : 실제로 에지들이 교차하지 않게 그린 그래프
• 예시
  • Complete Graph : => 까지만 플라나 그래프
  • Complete Bipartite Graph : => 은 플라나, 은 아님

지도 색칠하기 : 지도를 m가지 색으로 색칠 및 인접 영역은 서로 다른 색

• 지도 경계선을 공유하는 노드 사이의 에지를 그어주면? 플라나, 플레인 그래프
  • 지도 색칠하기 = 그래프 색칠하기

• 인접 노드 색깔이 아닌 색을 택해 나가는 형태로 구하며, 현재 1개의 답을 구한 상황이다.
• 모든 가능한 경우를 구하는 것이 목표이므로 나머지도 다 확인해서 해를 구하면 된다.

Hamiltonian Circuits(해밀토니안 회로)

한 정점에서 출발하여 그래프 각 정점을 한 번만 경유 하여 다시 출발 정점으로 돌아오는 경로

각 정점의 인접한 정점들을 가지고 상태공간트리 -> 깊이우선검색 -> Backtrack

• 그림처럼 각 정점의 인접한 정점들을 가지고 우선 상태공간트리를 이런식으로 만든다.
• 그 후 이 트리를 깊이우선검색을 하면서 가능한지 안되는지 백트래킹을 하면서 따져보면 된다.