3. 백트래킹(Backtracking): 효율적인 완전탐색의 기술

이미지 출처 - https://www.geeksforgeeks.org/backtracking-meaning-in-dsa/

"모든 가능성을 탐색해야 하지만 불필요한 경로는 빠르게 포기하는 지혜가 필요합니다. 백트래킹은 마치 미로에서 막다른 길을 만났을 때 이전 갈림길로 되돌아가는 전략적 탐색과 같습니다."

목차

• 백트래킹이란?
• 완전탐색과 백트래킹의 차이
• 백트래킹의 적용 조건
• 백트래킹의 동작 원리
• 재귀 함수를 활용한 백트래킹 구현
• 핵심 예제: 순열 구하기
• 시간복잡도 분석
• 백트래킹 문제 유형과 판단 기준
• 실전 구현 팁
• 대표적인 백트래킹 문제
• 결론

---

백트래킹이란?

백트래킹(Backtracking)은 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 알고리즘입니다. 가능한 모든 경로를 탐색하되, 특정 조건을 만족하지 않는 경로는 더 이상 탐색하지 않고 이전 단계로 돌아가는 방식으로 동작합니다.

백트래킹의 핵심은 불필요한 탐색을 줄이는 가지치기(Pruning) 과정에 있습니다. 이를 통해 완전탐색보다 효율적으로 해를 찾을 수 있습니다.

주요 특징:

• 재귀 함수를 기반으로 구현됨
• 결정 트리(Decision Tree)를 따라 깊이 우선 탐색(DFS)을 수행
• 현재까지의 부분 해가 조건을 만족하지 않으면 탐색을 중단하고 이전 상태로 돌아감

백트래킹은 다음과 같은 문제 해결에 효과적입니다:

• 순열과 조합 문제
• N-Queen 문제
• 스도쿠 풀이
• 부분 집합 문제
• 미로 찾기
• 암호 생성

---

완전탐색과 백트래킹의 차이

완전탐색(Brute Force)과 백트래킹은 모두 가능한 모든 경우의 수를 탐색한다는 공통점이 있지만, 중요한 차이점이 있습니다:

특성	완전탐색	백트래킹
탐색 방식	모든 경우의 수를 무차별적으로 탐색	유망한 경우만 선택적으로 탐색
효율성	비효율적	가지치기를 통한 효율성 향상
구현 방법	반복문, 재귀 등 다양한 방법	주로 재귀 함수 기반
적용 범위	제한된 크기의 문제	완전탐색으로 불가능한 크기의 문제도 해결 가능

백트래킹은 "유망하지 않은" 분기는 더 이상 탐색하지 않음으로써 탐색 공간을 크게 줄일 수 있습니다. 이는 마치 미로에서 막다른 길을 만났을 때 다시 돌아와 다른 경로를 탐색하는 것과 유사합니다.

---

백트래킹의 적용 조건

백트래킹 알고리즘은 다음과 같은 조건에서 효과적으로 적용할 수 있습니다:

1. 선택의 과정이 여러 단계로 이루어진 경우
   • 각 단계에서 선택할 수 있는 경우가 여러 가지인 경우
   • 예: N개의 숫자 중 M개 선택하기
2. 정해진 깊이(M)까지 선택을 진행해야 하는 경우
   • 특정 개수의 요소를 선택해야 하는 문제
   • 예: N개에서 M개를 뽑는 순열/조합
3. 동적인 깊이 탐색이 필요한 경우
   • 선택의 깊이가 정해지지 않은 경우
   • 예: 부분 집합 찾기, 미로 탐색
4. 탐색 과정에서 조건을 만족해야 하는 경우
   • 모든 솔루션이 아닌 특정 조건을 만족하는 솔루션만 필요한 경우
   • 예: N-Queen 문제, 스도쿠
5. 문제의 크기가 제한적인 경우
   • 보통 N이 20 이하인 경우 효과적
   • 백트래킹으로도 시간 초과가 발생할 수 있는 임계점을 고려

---

백트래킹의 동작 원리

백트래킹은 재귀적 구조를 기반으로 하며, 대략적인 동작 원리는 다음과 같습니다:

1. 상태 공간 트리 구성
   • 해를 찾기 위한 후보들을 트리 형태로 구성
2. 깊이 우선 탐색(DFS) 수행
   • 트리를 탐색하며 후보 해를 구성
3. 유망성 검사(Promising Test)
   • 현재까지 구성한 부분 해가 조건을 만족하는지 검사
4. 가지치기(Pruning)
   • 유망하지 않은 후보는 더 이상 탐색하지 않음
5. 백트래킹(되돌아가기)
   • 더 이상 탐색할 후보가 없거나 해를 찾은 경우 이전 단계로 돌아감

백트래킹 기본 구조

function backtrack(candidate):
    if 종료 조건을 만족한다면:
        해를 저장하거나 출력
        return

    for 모든 가능한 선택 in 현재 상태에서의 선택지:
        if 해당 선택이 유망하다면:
            선택을 추가
            backtrack(새로운 후보)
            선택을 제거 (백트래킹)

이 구조는 재귀 호출을 통해 깊이 우선으로 탐색하고, 조건에 맞지 않으면 이전 단계로 돌아가는 과정을 표현합니다.

---

재귀 함수를 활용한 백트래킹 구현

백트래킹은 주로 재귀 함수를 통해 구현됩니다. 재귀 함수를 사용하면 선택의 상태를 관리하고 이전 상태로 돌아가는 과정을 자연스럽게 표현할 수 있습니다.

백트래킹 구현의 핵심 요소

1. 상태 저장 구조
   • 현재까지의 선택을 저장하는 자료구조(보통 리스트 사용)
2. 방문 체크 배열
   • 이미 선택한 요소를 기록하는 배열
3. 종료 조건
   • 언제 재귀를 종료하고 결과를 처리할지 결정
4. 후보 선택과 제거
   • 후보를 선택하고, 재귀 호출이 끝난 후 선택을 제거(백트래킹)

---

핵심 예제: 순열 구하기

1부터 N까지의 숫자 중에서 중복 없이 M개를 선택하는 순열을 구하는 문제를 백트래킹으로 해결해보겠습니다.

문제 정의

• 입력: 두 정수 N, M (1 ≤ M ≤ N ≤ 8)
• 출력: 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 사전순으로 출력

접근 방법

1. result 리스트에 현재까지 선택한 숫자를 저장
2. visited 배열로 이미 선택한 숫자를 관리
3. 재귀 함수를 통해 백트래킹 구현

코드 구현

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
result = []
visited = [False] * (N + 1)  # 1부터 N까지 사용

def backtrack():
    # 종료 조건: M개의 숫자를 모두 선택했을 때
    if len(result) == M:
        print(' '.join(map(str, result)))
        return

    # 1부터 N까지의 모든 숫자에 대해
    for i in range(1, N + 1):
        # 아직 선택하지 않은 숫자라면
        if not visited[i]:
            # 선택 및 방문 처리
            visited[i] = True
            result.append(i)

            # 재귀 호출로 다음 숫자 선택
            backtrack()

            # 백트래킹: 선택 취소 및 방문 취소
            visited[i] = False
            result.pop()

backtrack()

동작 과정 예시 (N=3, M=2인 경우)

1. 빈 result 리스트로 시작
2. 숫자 1 선택: result = [1], visited = [F, T, F, F]
3. 재귀 호출, 숫자 2 선택: result = [1, 2], visited = [F, T, T, F]
4. M개(2개) 선택 완료, "1 2" 출력
5. 백트래킹: 숫자 2 제거, result = [1], visited = [F, T, F, F]
6. 숫자 3 선택: result = [1, 3], visited = [F, T, F, T]
7. M개(2개) 선택 완료, "1 3" 출력
8. 백트래킹: 숫자 3 제거, result = [1], visited = [F, T, F, F]
9. 더 이상 선택할 숫자가 없으므로 백트래킹: 숫자 1 제거, result = [], visited = [F, F, F, F]
10. 숫자 2 선택: result = [2], visited = [F, F, T, F]

이런 식으로 모든 가능한 순열(1 2, 1 3, 2 1, 2 3, 3 1, 3 2)을 생성합니다.

---

시간복잡도 분석

백트래킹의 시간복잡도는 문제의 특성과 가지치기 효율에 따라 달라질 수 있습니다. 최악의 경우 모든 가능한 경우를 탐색하게 되므로, 가능한 경우의 수와 동일한 시간복잡도를 가집니다.

주요 백트래킹 문제의 시간복잡도

1. 순열 문제: O(N! / (N-M)!)
   • N개 중 M개를 선택하는 순열의 경우의 수
2. 조합 문제: O(N! / (M! * (N-M)!))
   • N개 중 M개를 선택하는 조합의 경우의 수
3. N-Queen 문제: O(N!)
   • 가지치기를 통해 실제로는 이보다 훨씬 적은 경우만 탐색

백트래킹 적용 가능성 판단

일반적으로 다음과 같은 기준으로 백트래킹 적용 가능성을 판단할 수 있습니다:

• 최악의 경우 탐색해야 하는 경우의 수가 약 1억(10^8) 이하면 실행 시간 내에 해결 가능
• N이 작을수록(보통 N ≤ 15) 백트래킹 적용이 효과적
• 예: N = 10인 경우, 10! = 3,628,800으로 충분히 해결 가능

---

백트래킹 문제 유형과 판단 기준

백트래킹 문제인지 판단하는 기준과 주요 유형에 대해 알아보겠습니다.

백트래킹 문제 판단 기준

조건	백트래킹 적용 판단
수의 범위가 작다 (N ≤ 10~15)	백트래킹 사용 가능
모든 조합/순열을 요구한다	백트래킹 사용
결과가 특정 조건을 만족해야 한다	백트래킹 + 가지치기
탐색 중간에 조건을 확인해야 한다	백트래킹 적합

주요 백트래킹 문제 유형

1. 순열 문제
   • N개의 요소에서 M개를 선택하여 순서있게 나열하는 문제
2. 조합 문제
   • N개의 요소에서 M개를 선택하는 모든 경우를 구하는 문제
3. 부분 집합 문제
   • 집합의 모든 부분 집합을 구하는 문제
4. 제약 충족 문제
   • 특정 제약 조건을 만족하는 해를 찾는 문제
   • 예: N-Queen, 스도쿠, 암호 만들기
5. 결정 문제
   • 주어진 조건을 만족하는 해가 존재하는지 판단하는 문제
   • 예: 그래프 색칠 문제, 해밀턴 경로 문제

---

실전 구현 팁

백트래킹 알고리즘을 효과적으로 구현하기 위한 실전 팁을 소개합니다.

1. 재귀 함수 설계

• 종료 조건을 먼저 작성: 재귀 함수의 가장 위에 종료 조건을 명확히 작성
• 상태 변수 관리: 현재까지의 선택을 저장하는 상태 변수를 효율적으로 관리
• 매개변수 설계: 필요한 정보만 매개변수로 전달하여 함수 호출 오버헤드 최소화

2. 백트래킹 핵심 작성법

• 선택과 복구: 재귀 호출 전 선택, 호출 후 복구(백트래킹) 패턴 유지
• 방문 처리: 중복 방지를 위한 방문 처리 로직 구현
• 가지치기 최적화: 불필요한 탐색을 줄이는 조건 추가

3. 구현 시 주의사항

• 배열 크기 설정: visited 인덱스를 1부터 시작할 경우 크기를 N+1로 설정
• 입력값 처리: 무한 루프 방지를 위해 strip() 함수 사용
• 깊은 복사와 얕은 복사: 상태를 저장할 때 깊은 복사가 필요한 경우 주의
• 메모리 사용: 재귀 호출 깊이가 깊어질 경우 스택 오버플로우 발생 가능성 고려

4. 디버깅 전략

• 중간 상태 출력: 디버깅 시 함수 호출마다 현재 상태를 출력
• 작은 입력으로 테스트: 작은 크기의 입력으로 먼저 테스트 후 확장
• 종이에 트리 그리기: 복잡한 로직은 종이에 결정 트리를 그려보며 검증

---

대표적인 백트래킹 문제

백트래킹 학습을 위한 대표적인 문제들을 소개합니다.

기본 문제

1. 백준 15649번: N과 M (1)
   • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (순열)
   • 백트래킹의 기본적인 형태를 익히기 좋은 문제
2. 백준 15650번: N과 M (2)
   • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (조합)
   • 조합 형태의 백트래킹 문제

중급 문제

3. 백준 9663번: N-Queen
   • N×N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
   • 백트래킹의 대표적인 예제
4. 백준 2580번: 스도쿠
   • 9×9 스도쿠 퍼즐을 해결하는 문제
   • 제약 조건이 있는 백트래킹 문제

응용 문제

5. 백준 1759번: 암호 만들기
   • 주어진 알파벳으로 가능한 암호를 모두 구하는 문제
   • 조건이 있는 조합 문제
6. 백준 14888번: 연산자 끼워넣기
   • 숫자 사이에 연산자를 끼워넣어 최댓값과 최솟값을 구하는 문제
   • 모든 경우를 탐색하는 백트래킹 문제

---

결론

백트래킹은 완전탐색의 효율성을 높이는 강력한 알고리즘 기법입니다. 모든 가능한 경우를 고려하면서도, 불필요한 탐색은 빠르게 차단함으로써 문제 해결의 효율성을 크게 향상시킵니다.

백트래킹의 핵심 요소 정리

요소	설명
정의	조건을 만족하는 모든 경우의 수를 체계적으로 탐색하는 알고리즘
핵심 개념	가지치기(Pruning)를 통한 효율적인 탐색
종료 조건	원하는 깊이(M) 도달 시 or 특정 조건 만족 시
구현 방법	재귀 함수 + 상태 관리 + 방문 체크 배열
시간복잡도	문제에 따라 다름 (순열: O(N!), 조합: O(NCM) 등)
최적화 방법	효과적인 가지치기, 상태 공간 최소화

학습 전략

백트래킹은 문제 유형이 다양하고 난이도도 있기 때문에, 다음과 같은 학습 전략을 추천합니다:

1. 기본 개념을 확실히 이해하고 기본 패턴을 익히기
2. 쉬운 문제부터 시작하여 점차 난이도 높은 문제로 확장
3. 같은 유형의 문제를 여러 번 풀어보며 패턴 파악하기
4. 직접 결정 트리를 그려보며 알고리즘의 동작 과정 이해하기
5. 다른 사람의 코드를 분석하고 최적화 방법 학습하기

백트래킹은 코딩 테스트와 실무에서 모두 유용한 알고리즘 기법으로, 반복적인 연습을 통해 숙달하면 다양한 문제 해결에 큰 도움이 될 것입니다.

---

참고 자료

• 알고리즘 문제 해결 전략 (구종만 저)
• 백준 온라인 저지 - 백트래킹 문제 모음
• 프로그래머스 코딩테스트 연습
• 파이썬 알고리즘 인터뷰 (박상길 저)
• 알고리즘 시각화 도구 - VisuAlgo