본문으로 건너뛰기

백 트레킹

1. 백트래킹(Backtracking)​

백트래킹(Backtracking) 은 제약 조건 만족 문제에서 해를 찾기 위해,
조건을 만족하지 못하는 경로는 즉시 포기(가지치기)하고 이전 분기점으로 되돌아가는 탐색 기법입니다.
깊이 우선 탐색(DFS) 기반으로, 상태 공간 트리를 탐색하며 유망하지 않은 노드는 빠르게 제외합니다.
이 과정에서 이미 확인한 후보군은 다시 체크하지 않고, 다른 후보군으로 넘어가 최적의 해를 찾습니다.

깊이 우선 탐색(DFS)과의 연관성​

백트래킹은 연결된 노드를 따라 최대한 깊게 들어가는 "깊이 우선 탐색(DFS: Depth-First Search)" 방식을 활용합니다. 이는 상태 변화를 추적하기 용이하기 때문입니다.

백트래킹 상태 및 상태 공간 트리​

백트래킹 상태란 문제를 해결해나가는 과정에서 특정 순간의 모습을 의미하며, 시작 상태에서 출발하여 주어진 규칙에 따라 상태를 변화시키고 최종 상태에 도달하면 종료됩니다. (최종 상태는 ‘후보해(candidate solution)’라 부르기도 함)

예시: 배낭 문제(어떤 물건들이 들어있고 총 가치와 무게를 계산함), 오목 게임(게임 중 한 순간의 바둑판 모습)

상태 공간 트리(State Space Tree)는 가능한 모든 상태를 시각적으로 표현한 트리 구조입니다. 시작 상태에서 천이(transition)가 가능한 이후 상태를 자식 노드로 연결하고, 이 과정을 최종 상태에 이르기까지 반복합니다.

노드의 종류:

  • 유망한 노드 (promising node): 해답을 얻기 위해 자식 노드로 진행할 필요가 있는, 해답으로 이어질 가능성이 있는 노드
  • 유망하지 않은 노드 (nonpromising node): 더 이상 탐색할 필요가 없는 노드

가지치기(Pruning): 유망하지 않은 노드를 가능한 많이 걸러내는 전략이 중요합니다. 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법입니다.

백트래킹 알고리즘 구조 및 메모리 관리​

  • 상태 공간 트리의 탐색은 DFS 방식으로 이루어지며, 각 후보군을 DFS 방식으로 확인합니다.
  • promising(v) 함수를 통해 노드의 유망성을 판단하고, 유망하지 않으면 해당 분기(sub-tree)를 더 이상 탐색하지 않고 되돌아갑니다.
  • 순환 함수 호출 시 변하는 값만 파라미터로 넘기고, 변하지 않는 변수는 전역 변수로 선언하여 메모리 낭비를 줄입니다.
  • 실제 상태 공간 트리를 만드는 대신 탐색하는 노드의 상태를 배열에 기록하고 추적합니다.

핵심 개념​

  • 후보군에 제약 조건을 점진적으로 체크, 불가능하면 즉시 되돌아감
  • DFS 방식으로 상태 공간 트리 탐색
  • 가지치기(Pruning)로 탐색 효율화

예시​

  • 미로 찾기, 배낭 문제, 오목 게임 등

상태 공간 트리​

  • 가능한 모든 상태를 트리로 표현
  • 유망한 노드만 탐색, 유망하지 않으면 가지치기

알고리즘 구조​

  • DFS + 가지치기(promising 함수)
  • 메모리 효율을 위해 배열 등으로 상태 관리

2. N-여왕(N-Queen) 문제​

N-여왕 문제는 n × n 체스판에서 n개의 여왕을 서로 공격할 수 없도록 배치하는 문제입니다. (N ≥ 4에서만 해 존재)

문제 정의 및 예시​

  • 여왕은 가로, 세로, 대각선 방향으로 공격할 수 있으므로, N개의 여왕은 서로의 공격 범위에 놓이지 않아야 합니다.
  • 4-여왕 문제: 4x4 체스판에 4개의 여왕을 배치하는 과정을 통해 백트래킹의 작동 방식을 시각적으로 보여줌. n=4일 때 2가지 해답 노드가 있음.

백트래킹을 이용한 해결​

  • 배열로 상태 공간 트리 관리 (인덱스: 행, 값: 열)
  • 유망성 판단: 열, 두 대각선에 이미 퀸이 있으면 배치 불가 (beontour1, beontour2, beontour3 배열 활용)
  • qFunc(current): current번째 행에 퀸을 둘 수 있으면 다음 행으로 재귀 호출

분석

  • 상태 공간 트리의 노드 수(최악): (n^(n+1) - 1) / (n - 1)
  • 4-여왕: 341개, 8-여왕: 19,173,961개
  • 유망한 노드 수(최대): 4-여왕 65개, 8-여왕 109,601개
  • 실제 방문 노드 수는 백트래킹 가지치기로 훨씬 적음 (예: 8-여왕 DFS 15,721개 vs 백트래킹 2,057개)

3. 해밀턴 사이클(Hamiltonian Cycle)​

해밀턴 사이클은 **모든 정점을 한 번씩만 방문하고 출발점으로 돌아오는 경로(사이클)**를 찾는 문제입니다. (비방향성 그래프)

문제 정의 및 상태 공간 트리​

  • 해밀턴 경로: 그래프의 모든 정점을 단 한 번만 지나는 경로
  • 해밀턴 사이클: 한 정점에서 출발, 모든 정점 한 번씩 방문 후 출발점으로 복귀
  • 상태 공간 트리: 레벨 i의 노드는 i번째까지 방문한 정점들의 경로

유망하지 않은 노드 판별​

  • i번째 방문한 정점이 이전 정점과 인접하지 않음
  • 마지막 정점이 출발점과 인접하지 않음
  • 이미 방문한 정점 재방문

백트래킹 알고리즘 및 분석​

  • 1차원 배열로 경로 관리 (인덱스: 방문 순서, 값: 정점)
  • 상태 공간 트리의 노드 수(최악): 1 + (n-1) + (n-1)^2 + ... + (n-1)^(n-1)
  • 4정점: 40개, 8정점: 960,800개
  • 유망 노드 수는 입력 그래프에 따라 다름 (전체 탐색 필요할 수도 있음)

4. 그래프 채색(Graph Coloring)​

그래프 채색은 정점, 간선, 면을 기준으로 인접한 구성 요소가 같은 색이 되지 않도록 색칠하는 문제입니다. (일반적으로 정점 채색)

문제 정의 및 상태 공간 트리​

  • 정점 채색: 인접한 두 정점이 같은 색을 갖지 않도록 모든 정점을 칠하는 문제
  • 루프를 가지는 정점: 채색 불가
  • 목표: 최대 n개의 색으로 정점 채색 가능 여부 결정 (색은 1, 2, 3 등 정수)
  • 상태 공간 트리: 레벨 i의 노드는 정점 1~i까지 채색한 상태

유망하지 않은 노드 판별​

  • 인접한 정점이 같은 색이면 가지치기
  • 해답 노드 발견 시 실행 중단 (결정 문제)

백트래킹 알고리즘 및 분석​

  • 1차원 배열로 상태 관리 (인덱스: 방문 순서, 값: 정점의 색)
  • 상태 공간 트리의 노드 수: (k^(n+1) - 1) / (k - 1)
  • 실제 방문 노드는 효율적 가지치기로 훨씬 적음
  • 유망 노드 수는 입력 그래프에 따라 다름

응용 분야​

  • 컴파일러 레지스터 할당
  • 스도쿠
  • 다양한 스케줄링 문제

5. 브루트 포스(Brute Force)​

브루트 포스는 가능한 모든 경우의 수를 탐색하여 해를 찾는 완전 탐색 알고리즘입니다.

개념 및 해결 방법​

  • 모든 경우의 수를 탐색하여 해를 찾는 단순하고 직접적인 방법 (단순법)
  • 선형 검색, DFS, BFS 등 다양한 구조에 적용
  • 문자열 검색: 텍스트의 각 위치에서 패턴과 일치하는지 순차적으로 비교

장점 및 종류​

  • 구현이 쉽고, 정답 확률이 높음 (모든 경우의 수를 탐색하므로)
  • 선형구조 탐색: 순차 탐색
  • 비선형구조 탐색: DFS, BFS

시간 복잡도​

  • 문자열 검색: 텍스트 길이 n, 패턴 길이 m일 때 O(mn)
  • 실제로는 패턴이 짧거나 없으면 O(n)에 가까움