백트래킹 - 1편

2025년 04월 30일

AlgorithmBacktracking재귀함수Programmers
백트래킹 - 1편

📙 백트래킹 알고리즘(Backtracking)

정의 : 모든 가능한 경우를 탐색하되, 현재 경로가 정답이 될 가능성이 없으면 바로 되돌아가 다른 경로를 탐색하는 기법

  • 깊이 우선 탐색(DFS) 방식으로 단계적으로 경로를 만들어 나간다.
  • 조건을 만족하지 않으면 그 경로를 가지치기(Pruning)하여 더 이상 탐색하지 않는다.
  • 이전 단계로 되돌아가는 것(backtracking) 이 핵심.

장점: 불필요한 경로 탐색을 줄여서 효율을 높일 수 있다.

  • 가지치기를 얼마나 효과적으로 하느냐에 따라 알고리즘의 성능이 결정됨.
  • 완전 탐색(brute force) 에 비해 많은 경로를 조기에 중단하므로 효율적이다.

📗 주로 사용되는 자료구조

  1. 보통 재귀 호출 을 통해 구현되고, 재귀 호출 자체가 콜 스택(call stack) 을 이용하므로 스택 구조를 자연스럽게 사용한다.
  2. 재귀를 사용하면 함수가 호출될 때 마다 스택 프레임 이 쌓이고, 함수 종료시 사라지면서 자동으로 이전 상태로 돌아온다.
  3. 따라서, 별도의 자료구조 없이도 상태 저장과 복원을 수행한다.

📙 백트래킹 알고리즘 ― 기본 흐름

1. 재귀 함수 정의

  • 매개변수: path(현재까지 선택한 값들), start (다음에 시작할 숫자나 위치) 등

2. 종료 조건(base case) 체크

  • 목표 길이나 조건을 만족하면
    1. 결과를 기록하고 (정답 배열에 추가 또는 카운트 증가)
    2. return으로 재귀 호출을 종료한다.

3. 가지치기(pruning)

  • 현재 path로는 정답이 될 수 없다고 판단되면 바로 return하여 해당 경로 탐색을 중단한다.

4. 후보 순회

  • 가능한 선택지(숫자, 위치 등)를 반복문으로 순회하며
    1. 선택 : 값을 path에 추가하거나 방문 표시
    2. 재귀 호출: 다음 단계로 진행
    3. 되돌아가기 : 마지막 선택을 취소하거나 방문 표시 해제

5. 시작 호출

  • 빈 path와 초기 start값으로 재귀 함수를 호출해 탐색을 시작한다.

핵심: "선택 ➡ 재귀 호출 ➡ 상태 복원" 을 반복하며,
종료 조건과 가지치기로 탐색 공간을 줄인다.

📘 백트래킹 적용 사례

  • N-Queens 문제: N×N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 방법 찾기
  • 스도쿠 풀이: 9×9 그리드에 1~9 숫자를 규칙에 맞게 채우기
  • 부분집합 구하기: 집합의 모든 부분집합을 찾기
  • 조합/순열 생성: n개 중 r개를 뽑는 모든 경우의 수 생성
  • 경로 탐색 문제: 미로 찾기, 최단 경로 등의 탐색
  • 그래프 색칠 문제: 인접한 노드가 같은 색을 갖지 않도록 색칠하기

📙 백트래킹의 시간 복잡도

  • 최악의 경우: O(b^d) - b는 각 단계에서의 선택지 수, d는 최대 깊이
  • 실제 성능: 가지치기 효율에 따라 크게 달라짐
  • 공간 복잡도: O(d) - 재귀 호출 스택의 최대 깊이

예제코드 - 비밀 코드 해독 문제

💡 문제 요약: 1부터 n까지의 정수 중 5개를 선택하여 비밀 코드를 맞추는 문제. 여러 번의 시도와 그 결과(각 시도마다 몇 개의 숫자가 일치하는지)를 바탕으로 가능한 비밀 코드 조합의 개수를 구해야 함

1. 함수 정의

  • recursion(comb, start)
  • comb : 지금까지 선택한 숫자 배열
  • start : 다음에 시작할 숫자

2. 선택

  • 반복문에서 숫자 i 를 선택할 때 comb.push(i) 로 배열에 추가

3. 종료 조건 + 가지치기

  • if (comb.length === 5)
    1. 각 시도와 시스템 응답을 비교하여 일치하는 숫자 갯수 계산
    2. 모든 조건을 만족하면 count++ 로 유효한 조합 카운트
    3. 하나라도 조건을 만족하지 않으면 즉시 return으로 탐색 중단

4. 다음 단계로 재귀 호출

  • for (let i = start; i <= n; i++)
  • 숫자 선택 → recursion(comb, i + 1) 호출로 다음 단계 진행

5. 상태 복원(되돌아가기)

  • 재귀 호출이 끝나면 comb.pop()으로 마지막 선택 제거
  • 이로써 같은 단계에서 다른 숫자를 선택할 준비 완료

6. 시작과 결과

  • recursion([], 1) 로 탐색 시작
  • 탐색이 끝나면 유효한 조합 개수 count반환

참고 코드)