백트래킹 개념, 유망 함수와 가지치기, 예시 문제로 이해하기

백트래킹 개념 이해하기

완전 탐색과 그 문제점

완전 탐색(Brute Force)은 가능한 모든 경우를 하나씩 전부 확인하여 문제를 해결하는 알고리즘이다.

 

대표적인 방식으로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 방식이 있다.

 

아래 그림은 루트 A에서 시작해 자식 노드 B, C, D와 그 아래 레벨을 가진 작은 트리를 대상으로, DFS와 BFS가 동일한 공간을 어떻게 “완전 탐색”하는지 보여 준다.

 

<!-- DFS -->
<svg width="220" height="170" xmlns="http://www.w3.org/2000/svg" style="font-family:'Pretendard';">
  <text x="0" y="15" font-size="14">DFS</text>
  <!-- nodes -->
  <circle cx="110" cy="40"  r="13" fill="#fff" stroke="#333" />
  <text x="106" y="45" font-size="12">A</text>
  <circle cx="60"  cy="90"  r="13" fill="#fff" stroke="#333" />
  <text x="56"  y="95" font-size="12">B</text>
  <circle cx="160" cy="90"  r="13" fill="#fff" stroke="#333" />
  <text x="156" y="95" font-size="12">C</text>
  <circle cx="110" cy="140" r="13" fill="#fff" stroke="#333" />
  <text x="106" y="145" font-size="12">D</text>
  <!-- edges -->
  <line x1="110" y1="53"  x2="60"  y2="77"  stroke="#888" />
  <line x1="110" y1="53"  x2="160" y2="77"  stroke="#888" />
  <line x1="60"  y1="103" x2="110" y2="127" stroke="#888" />
  <!-- visit order -->
  <text x="115" y="30"  font-size="10" fill="#c00">1</text>
  <text x="40"  y="100" font-size="10" fill="#c00">2</text>
  <text x="90"  y="150" font-size="10" fill="#c00">3</text>
  <text x="175" y="100" font-size="10" fill="#c00">4</text>
</svg>

<!-- BFS -->
<svg width="220" height="170" xmlns="http://www.w3.org/2000/svg" style="font-family:'Pretendard';">
  <text x="0" y="15" font-size="14">BFS</text>
  <!-- nodes -->
  <circle cx="110" cy="40"  r="13" fill="#fff" stroke="#333" />
  <text x="106" y="45" font-size="12">A</text>
  <circle cx="60"  cy="90"  r="13" fill="#fff" stroke="#333" />
  <text x="56"  y="95" font-size="12">B</text>
  <circle cx="160" cy="90"  r="13" fill="#fff" stroke="#333" />
  <text x="156" y="95" font-size="12">C</text>
  <circle cx="110" cy="140" r="13" fill="#fff" stroke="#333" />
  <text x="106" y="145" font-size="12">D</text>
  <!-- edges -->
  <line x1="110" y1="53"  x2="60"  y2="77"  stroke="#888" />
  <line x1="110" y1="53"  x2="160" y2="77"  stroke="#888" />
  <line x1="60"  y1="103" x2="110" y2="127" stroke="#888" />
  <!-- visit order -->
  <text x="115" y="30"  font-size="10" fill="#00c">1</text>
  <text x="40"  y="100" font-size="10" fill="#00c">2</text>
  <text x="175" y="100" font-size="10" fill="#00c">3</text>
  <text x="90"  y="150" font-size="10" fill="#00c">4</text>
</svg>

 

깊이 우선 탐색은 루트에서 출발해 한 방향으로 가능한 한 깊이 내려간 뒤 더 내려갈 수 없으면 직전에 갈림길이 있던 노드로 “되돌아가” 다른 경로를 탐색한다. 반면 너비 우선 탐색은 같은 깊이에 있는 노드들을 모두 방문한 뒤 다음 깊이로 내려간다.

 

예를 들어, 4자리 자물쇠 비밀번호를 맞추는 경우를 생각해 보자. 다음과 같이 모든 경우를 차례로 시도할 것이다.

 

0000, 0001, 0002, ..., 9997, 9998, 9999

 

이처럼 완전 탐색은 해결해야 할 경우의 수가 많아질수록 급격히 효율이 떨어진다. 특히 숫자가 한자리만 늘어나도 시도해야 하는 경우의 수가 10배나 증가하게 되어, 현실적으로 시간이 매우 오래 걸린다.

 

이 문제를 어떻게 해결할 수 있을까?

백트래킹이란?

백트래킹(Backtracking)은 해결 과정에서 특정 경로가 해답으로 이어지지 않는다고 판단되었을 때, 그 지점에서 더 이상 진행하지 않고 이전 단계로 되돌아가 다른 가능성을 탐색하는 방법이다.

 

즉, 백트래킹은 “뒤로 물러난다”는 행위 자체를 의미하며, 백트래킹 알고리즘은 이러한 행위를 체계적으로 사용해 탐색 공간을 줄이는 알고리즘을 가리킨다. 일반적으로 “백트래킹으로 푼다”라고 말할 때는 백트래킹 알고리즘을 적용한다는 뜻으로 통용된다.

 

앞서 살펴본, 깊이 우선 탐색이나 너비 우선 탐색이 완전 탐색으로 모든 경우의 수를 찾는 것 대비, 백트래킹을 사용하면 효율적으로 탐색량을 줄일 수 있다.

 

예를 들어, 퍼즐 조각 맞추기를 생각해 보자. 그림이 완성되려면 조각이 드러내는 무늬가 서로 이어져야 한다. 첫 번째 조각을 놓은 뒤 두 번째 조각을 시험 삼아 맞춰 보았는데 무늬가 이어지지 않는다면, 그대로 진행하지 않고 두 번째 조각을 바꿔 끼워 본다. 이처럼 “이 조각은 틀렸다”라는 판단 기준을 세운 뒤 곧바로 되돌아가는 것이 백트래킹의 핵심 사고 방식이다.

 

<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg">
  <defs>
    <!-- 그라데이션 정의 -->
    <linearGradient id="correctGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#4CAF50;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#45a049;stop-opacity:1" />
    </linearGradient>

    <linearGradient id="wrongGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#f44336;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#d32f2f;stop-opacity:1" />
    </linearGradient>

    <linearGradient id="tryGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#ff9800;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#f57c00;stop-opacity:1" />
    </linearGradient>
  </defs>

  <!-- 배경 -->
  <rect width="800" height="600" fill="#f5f5f5"/>

  <!-- 제목 -->
  <text x="400" y="40" text-anchor="middle" font-family="Arial, sans-serif" font-size="24" font-weight="bold" fill="#333">백트래킹: 퍼즐 조각 맞추기</text>

  <!-- 단계 1: 첫 번째 조각 배치 -->
  <g id="step1">
    <text x="50" y="100" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#333">1단계: 첫 번째 조각 배치</text>

    <!-- 퍼즐 베이스 -->
    <rect x="50" y="120" width="200" height="150" fill="#ddd" stroke="#999" stroke-width="2" rx="10"/>

    <!-- 첫 번째 조각 (올바른 위치) -->
    <path d="M 60 130 L 140 130 C 150 120 150 140 140 150 L 60 150 Z" fill="url(#correctGrad)" stroke="#333" stroke-width="2"/>

    <!-- 무늬 표시 -->
    <circle cx="80" cy="140" r="8" fill="#fff"/>
    <circle cx="100" cy="140" r="8" fill="#fff"/>
    <circle cx="120" cy="140" r="8" fill="#fff"/>
  </g>

  <!-- 단계 2: 두 번째 조각 시도 (실패) -->
  <g id="step2">
    <text x="300" y="100" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#333">2단계: 두 번째 조각 시도 (실패)</text>

    <!-- 퍼즐 베이스 -->
    <rect x="300" y="120" width="200" height="150" fill="#ddd" stroke="#999" stroke-width="2" rx="10"/>

    <!-- 첫 번째 조각 -->
    <path d="M 310 130 L 390 130 C 400 120 400 140 390 150 L 310 150 Z" fill="url(#correctGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="330" cy="140" r="8" fill="#fff"/>
    <circle cx="350" cy="140" r="8" fill="#fff"/>
    <circle cx="370" cy="140" r="8" fill="#fff"/>

    <!-- 두 번째 조각 (틀린 위치) -->
    <path d="M 390 130 C 380 120 380 140 390 130 L 470 130 L 470 150 L 390 150 Z" fill="url(#wrongGrad)" stroke="#333" stroke-width="2"/>
    <rect x="410" y="135" width="8" height="8" fill="#fff"/>
    <rect x="430" y="135" width="8" height="8" fill="#fff"/>
    <rect x="450" y="135" width="8" height="8" fill="#fff"/>

    <!-- 불일치 표시 -->
    <line x1="390" y1="120" x2="390" y2="160" stroke="red" stroke-width="3"/>
    <text x="395" y="115" font-family="Arial, sans-serif" font-size="12" fill="red">무늬 불일치!</text>
  </g>

  <!-- 단계 3: 백트래킹 -->
  <g id="step3">
    <text x="550" y="100" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#333">3단계: 백트래킹</text>

    <!-- 퍼즐 베이스 -->
    <rect x="550" y="120" width="200" height="150" fill="#ddd" stroke="#999" stroke-width="2" rx="10"/>

    <!-- 첫 번째 조각 -->
    <path d="M 560 130 L 640 130 C 650 120 650 140 640 150 L 560 150 Z" fill="url(#correctGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="580" cy="140" r="8" fill="#fff"/>
    <circle cx="600" cy="140" r="8" fill="#fff"/>
    <circle cx="620" cy="140" r="8" fill="#fff"/>

    <!-- 되돌아가는 화살표 -->
    <path d="M 640 160 Q 680 180 640 200" fill="none" stroke="#ff9800" stroke-width="3" marker-end="url(#arrowhead)"/>
    <text x="650" y="175" font-family="Arial, sans-serif" font-size="12" fill="#ff9800">되돌아가기</text>
  </g>

  <!-- 단계 4: 올바른 조각 찾기 -->
  <g id="step4">
    <text x="50" y="350" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#333">4단계: 다른 조각으로 재시도</text>

    <!-- 퍼즐 베이스 -->
    <rect x="50" y="370" width="200" height="150" fill="#ddd" stroke="#999" stroke-width="2" rx="10"/>

    <!-- 첫 번째 조각 -->
    <path d="M 60 380 L 140 380 C 150 370 150 390 140 400 L 60 400 Z" fill="url(#correctGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="80" cy="390" r="8" fill="#fff"/>
    <circle cx="100" cy="390" r="8" fill="#fff"/>
    <circle cx="120" cy="390" r="8" fill="#fff"/>

    <!-- 두 번째 조각 (올바른 선택) -->
    <path d="M 140 380 C 150 370 150 390 140 400 L 220 400 L 220 380 Z" fill="url(#correctGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="160" cy="390" r="8" fill="#fff"/>
    <circle cx="180" cy="390" r="8" fill="#fff"/>
    <circle cx="200" cy="390" r="8" fill="#fff"/>

    <!-- 성공 표시 -->
    <circle cx="225" cy="390" r="15" fill="#4CAF50"/>
    <path d="M 220 390 L 225 395 L 235 385" fill="none" stroke="#fff" stroke-width="2"/>
  </g>

  <!-- 백트래킹 알고리즘 설명 -->
  <g id="explanation">
    <text x="300" y="350" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#333">백트래킹 핵심 사고방식</text>

    <rect x="300" y="370" width="450" height="200" fill="#fff" stroke="#ddd" stroke-width="1" rx="5"/>

    <text x="320" y="400" font-family="Arial, sans-serif" font-size="14" fill="#333">1. 조건 확인: 현재 선택이 올바른가?</text>
    <text x="320" y="425" font-family="Arial, sans-serif" font-size="14" fill="#333">2. 판단 기준: "이 조각은 틀렸다"</text>
    <text x="320" y="450" font-family="Arial, sans-serif" font-size="14" fill="#333">3. 즉시 되돌아가기: 잘못된 경로 포기</text>
    <text x="320" y="475" font-family="Arial, sans-serif" font-size="14" fill="#333">4. 다른 선택 시도: 새로운 가능성 탐색</text>
    <text x="320" y="500" font-family="Arial, sans-serif" font-size="14" fill="#333">5. 반복: 해답을 찾을 때까지 계속</text>

    <rect x="320" y="520" width="400" height="35" fill="#e3f2fd" stroke="#2196f3" stroke-width="1" rx="3"/>
    <text x="330" y="540" font-family="Arial, sans-serif" font-size="12" fill="#1976d2" font-style="italic">
      "틀렸다면 즉시 되돌아가라" - 백트래킹의 핵심
    </text>
  </g>

  <!-- 화살표 마커 정의 -->
  <defs>
    <marker id="arrowhead" markerWidth="10" markerHeight="7" 
            refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#ff9800"/>
    </marker>
  </defs>
</svg>

 

그렇다면 깊이 우선 탐색을 수행하다 막다른 길에서 부모 노드로 되돌아가는 행동 역시 “백트래킹”이라 할 수 있을까? 맞다. 다만 순수 DFS와 달리 백트래킹 알고리즘은 "해가 존재할 가능성"을 판별하는 명시적 기준(제약 조건)을 두고, 기준에 어긋나는 분기는 즉시 잘라 내어 탐색량을 줄인다.

 

앞서 살펴본 비밀번호 예시를 다시 들어 보자. 비밀번호 힌트로 다음과 같이 주어졌다고 해보자.

비밀번호는 반드시 99로 시작한다.

이 조건이 주어지면, 백트래킹 알고리즘은 탐색 시작 단계에서 00부터 98로 시작하는 모든 조합을 아예 건너뛴다.

 

9900, 9901, 9902, ..., 9998, 9999

 

즉, 백트래킹은 이를 미리 인지하고 정답이 될 수 없는 후보는 애초에 고려하지 않음으로써 탐색 범위를 크게 줄일 수 있는 것이다. 조건이 많아질수록, 그리고 각 조건이 초기에 걸러 내는 분기점이 높을수록 백트래킹의 성능 이득은 더욱 커진다.

 

“가능성 없는 길을 빠르게 버리고 되돌아간다”는 것이 핵심 아이디어다.

백트래킹이 필요한 문제들

백트래킹은 주로 다음과 같은 문제들에서 효과적으로 활용된다.

• 조합 문제: 특정 조건을 만족하는 요소들의 조합을 찾을 때
• 순열 문제: 특정한 순서로 요소들을 배치하거나 나열할 때
• 스도쿠 문제: 빈칸을 채우되 조건을 만족시키는 숫자를 찾을 때
• 미로 찾기 문제: 목적지까지의 경로를 찾을 때
• N-Queen 문제: 체스판 위에 퀸을 서로 공격하지 못하게 배치할 때
  
  

---

유망함수와 가지치기(pruning)란?

앞서 살펴보았듯이, 탐색 트리를 전부 뒤져야 하는 완전 탐색과 달리, 백트래킹은 “해답으로 이어질 가능성이 있는 갈림길만 깊게 파고드는” 방식을 택한다.

 

이 때 가능성을 평가하는 도구가 유망함수(promising function),

 

그 평가 결과에 따라 탐색 일부를 잘라 내는 동작이 가지치기(pruning)이다.

 

 

1) 유망함수 ─ “계속 들어갈 만한가?”

백트래킹에서 가장 핵심적인 요소 중 하나가 바로 유망함수이다. 유망함수는 탐색을 계속 진행할 가치가 있는지, 아니면 여기서 멈추고 되돌아가야 하는지를 결정하는 기준이 된다. 쉽게 말해 "앞으로 더 나아갔을 때 해답을 찾을 가능성이 있는가?"를 판단하는 역할을 한다.

 

예를 들어 숫자 조합 문제에서 "현재까지 선택한 숫자들의 합이 목표 값보다 이미 커졌다"면 더 이상 추가로 숫자를 선택해봤자 목표를 만족시킬 수 없으므로 이때 유망함수는 "더 이상 유망하지 않다(non-promising)"고 판단한다.

 

즉, 유망함수는 백트래킹 과정에서 탐색할 가치가 있는지 없는지를 빠르게 판단하는 필터 역할을 한다고 볼 수 있다.

 

예를 들면,

• N-Queen ⇒ “서로 공격하지 않는다”
• 스도쿠 ⇒ “같은 행·열·3×3 블록에 중복 숫자가 없다”
• 그래프 색칠 ⇒ “인접 정점이 같은 색이 아니다”

2) 가지치기 ─ “가능성 없다면 즉시 포기”

유망함수를 활용해 "탐색할 가치가 없음"이 확인되었다면, 즉 유망함수 결과가 False라면, 그 탐색 경로를 즉시 중단하는 행위를 가지치기(pruning)라고 한다. 프루닝은 말 그대로 나무의 가지를 잘라내는 행위에서 유래한 용어로, 탐색의 불필요한 부분을 잘라내어 탐색 공간을 줄이는 기법이다.

 

즉, 가지치기는 유망함수의 결과를 기반으로, 탐색의 효율성을 극대화하는 실질적인 행동이다.

 

유망하지 않다고 판단된 노드 이후의 자식 노드나 하위 경로는 더 이상 고려하지 않고 즉각적으로 버리게 된다.

<svg viewBox="0 0 900 700" xmlns="http://www.w3.org/2000/svg">
  <defs>
    <!-- 그라데이션 정의 -->
    <linearGradient id="startGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#2196F3;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#1976D2;stop-opacity:1" />
    </linearGradient>

    <linearGradient id="validGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#4CAF50;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#45a049;stop-opacity:1" />
    </linearGradient>

    <linearGradient id="prunedGrad" x1="0%" y1="0%" x2="100%" y2="100%">
      <stop offset="0%" style="stop-color:#f44336;stop-opacity:1" />
      <stop offset="100%" style="stop-color:#d32f2f;stop-opacity:1" />
    </linearGradient>

    <!-- 화살표 마커 -->
    <marker id="arrowhead" markerWidth="10" markerHeight="7" 
            refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#333"/>
    </marker>

    <marker id="cutArrow" markerWidth="12" markerHeight="9" 
            refX="11" refY="4.5" orient="auto">
      <polygon points="0 0, 12 4.5, 0 9" fill="#f44336"/>
    </marker>
  </defs>

  <!-- 배경 -->
  <rect width="900" height="700" fill="#f8f9fa"/>

  <!-- 제목 -->
  <text x="450" y="40" text-anchor="middle" font-family="Arial, sans-serif" font-size="24" font-weight="bold" fill="#333">가지치기(Pruning) - "가능성 없다면 즉시 포기"</text>

  <!-- 메인 트리 구조 -->
  <g id="main-tree">
    <!-- 루트 노드 -->
    <circle cx="450" cy="100" r="25" fill="url(#startGrad)" stroke="#333" stroke-width="2"/>
    <text x="450" y="106" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" font-weight="bold" fill="white">START</text>

    <!-- 레벨 1 연결선 -->
    <line x1="450" y1="125" x2="300" y2="175" stroke="#333" stroke-width="2"/>
    <line x1="450" y1="125" x2="450" y2="175" stroke="#333" stroke-width="2"/>
    <line x1="450" y1="125" x2="600" y2="175" stroke="#333" stroke-width="2"/>

    <!-- 레벨 1 노드들 -->
    <!-- 유망하지 않은 노드 (가지치기 대상) -->
    <circle cx="300" cy="200" r="20" fill="url(#prunedGrad)" stroke="#333" stroke-width="2"/>
    <text x="300" y="206" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" font-weight="bold" fill="white">X</text>
    <text x="300" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" fill="#f44336" font-weight="bold">유망 X</text>

    <!-- 유망한 노드들 -->
    <circle cx="450" cy="200" r="20" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <text x="450" y="206" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" font-weight="bold" fill="white">O</text>
    <text x="450" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" fill="#4CAF50" font-weight="bold">유망 O</text>

    <circle cx="600" cy="200" r="20" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <text x="600" y="206" text-anchor="middle" font-family="Arial, sans-serif" font-size="10" font-weight="bold" fill="white">O</text>
    <text x="600" y="240" text-anchor="middle" font-family="Arial, sans-serif" font-size="12" fill="#4CAF50" font-weight="bold">유망 O</text>
  </g>

  <!-- 가지치기된 부분 (회색으로 표시) -->
  <g id="pruned-section" opacity="0.3">
    <!-- 가지치기된 하위 노드들 -->
    <line x1="300" y1="220" x2="250" y2="280" stroke="#999" stroke-width="1" stroke-dasharray="5,5"/>
    <line x1="300" y1="220" x2="300" y2="280" stroke="#999" stroke-width="1" stroke-dasharray="5,5"/>
    <line x1="300" y1="220" x2="350" y2="280" stroke="#999" stroke-width="1" stroke-dasharray="5,5"/>

    <circle cx="250" cy="300" r="15" fill="#ccc" stroke="#999" stroke-width="1"/>
    <circle cx="300" cy="300" r="15" fill="#ccc" stroke="#999" stroke-width="1"/>
    <circle cx="350" cy="300" r="15" fill="#ccc" stroke="#999" stroke-width="1"/>

    <!-- 더 깊은 레벨들 -->
    <line x1="250" y1="315" x2="225" y2="355" stroke="#999" stroke-width="1" stroke-dasharray="5,5"/>
    <line x1="250" y1="315" x2="275" y2="355" stroke="#999" stroke-width="1" stroke-dasharray="5,5"/>
    <circle cx="225" cy="370" r="12" fill="#ccc" stroke="#999" stroke-width="1"/>
    <circle cx="275" cy="370" r="12" fill="#ccc" stroke="#999" stroke-width="1"/>
  </g>

  <!-- 활성 탐색 경로 -->
  <g id="active-paths">
    <!-- 유망한 노드들의 하위 탐색 -->
    <line x1="450" y1="220" x2="400" y2="280" stroke="#4CAF50" stroke-width="2"/>
    <line x1="450" y1="220" x2="450" y2="280" stroke="#4CAF50" stroke-width="2"/>
    <line x1="450" y1="220" x2="500" y2="280" stroke="#4CAF50" stroke-width="2"/>

    <circle cx="400" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="450" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="500" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>

    <line x1="600" y1="220" x2="550" y2="280" stroke="#4CAF50" stroke-width="2"/>
    <line x1="600" y1="220" x2="600" y2="280" stroke="#4CAF50" stroke-width="2"/>
    <line x1="600" y1="220" x2="650" y2="280" stroke="#4CAF50" stroke-width="2"/>

    <circle cx="550" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="600" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
    <circle cx="650" cy="300" r="15" fill="url(#validGrad)" stroke="#333" stroke-width="2"/>
  </g>

  <!-- 가지치기 표시 -->
  <g id="pruning-indicator">
    <!-- 큰 X 표시 -->
    <line x1="280" y1="260" x2="320" y2="340" stroke="#f44336" stroke-width="4"/>
    <line x1="320" y1="260" x2="280" y2="340" stroke="#f44336" stroke-width="4"/>

    <!-- 가지치기 라벨 -->
    <rect x="200" y="350" width="200" height="30" fill="#ffebee" stroke="#f44336" stroke-width="1" rx="5"/>
    <text x="300" y="370" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" font-weight="bold" fill="#f44336">❌ CUT (가지치기)</text>
  </g>

  <!-- 탐색 진행 표시 -->
  <g id="exploration-indicator">
    <text x="450" y="350" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" fill="#4CAF50" font-weight="bold">↙ 하위 탐색 계속</text>
    <text x="600" y="350" text-anchor="middle" font-family="Arial, sans-serif" font-size="14" fill="#4CAF50" font-weight="bold">↘ 하위 탐색 계속</text>
  </g>

  <!-- 유망함수 설명 박스 -->
  <g id="explanation-box">
    <rect x="50" y="420" width="800" height="120" fill="#fff" stroke="#ddd" stroke-width="2" rx="10"/>
    <text x="70" y="450" font-family="Arial, sans-serif" font-size="18" font-weight="bold" fill="#333">유망함수(Promising Function)의 역할</text>

    <text x="70" y="480" font-family="Arial, sans-serif" font-size="14" fill="#333">• 각 노드에서 "이 경로가 해답으로 이어질 가능성이 있는가?"를 판단</text>
    <text x="70" y="500" font-family="Arial, sans-serif" font-size="14" fill="#333">• 유망함수 결과가 False → 즉시 가지치기 실행</text>
    <text x="70" y="520" font-family="Arial, sans-serif" font-size="14" fill="#333">• 불필요한 탐색을 조기에 차단하여 탐색 공간을 기하급수적으로 감소</text>
  </g>

  <!-- 효과 설명 -->
  <g id="effect-explanation">
    <rect x="50" y="560" width="380" height="120" fill="#e8f5e8" stroke="#4CAF50" stroke-width="2" rx="10"/>
    <text x="70" y="590" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#2e7d32">✓ 가지치기의 효과</text>
    <text x="70" y="615" font-family="Arial, sans-serif" font-size="13" fill="#2e7d32">• 탐색 노드 수 기하급수적 감소</text>
    <text x="70" y="635" font-family="Arial, sans-serif" font-size="13" fill="#2e7d32">• 시간 복잡도 대폭 개선</text>
    <text x="70" y="655" font-family="Arial, sans-serif" font-size="13" fill="#2e7d32">• 메모리 사용량 절약</text>

    <rect x="470" y="560" width="380" height="120" fill="#fff3e0" stroke="#ff9800" stroke-width="2" rx="10"/>
    <text x="490" y="590" font-family="Arial, sans-serif" font-size="16" font-weight="bold" fill="#e65100">⚡ 성능 향상 조건</text>
    <text x="490" y="615" font-family="Arial, sans-serif" font-size="13" fill="#e65100">• 조건이 강할수록 성능 향상 극적</text>
    <text x="490" y="635" font-family="Arial, sans-serif" font-size="13" fill="#e65100">• 초기 단계에서 많은 판단을 내릴수록 효과적</text>
    <text x="490" y="655" font-family="Arial, sans-serif" font-size="13" fill="#e65100">• 정확한 유망함수 설계가 핵심</text>
  </g>
</svg>

3) 유망함수와 가지치기의 관계

두 개념은 별개의 개념이 아니라 서로 밀접히 연결된 관계이다.

• 유망함수는 탐색의 가치 여부를 결정하는 판단의 기준이고,
• 가지치기는 이 판단을 바탕으로 탐색을 중단하고 이전 단계로 되돌아가는 실제적인 행동이다.

비유적으로 보면 유망함수는 탐색의 길에서 "이 길이 계속 갈 만한 길인가?"라고 묻는 역할을 하고, 가지치기는 유망함수가 "갈 가치가 없다"고 하면 즉각 "되돌아가는" 행동을 취하는 것이다.

4) 예시

간단한 숫자 합 예시를 들어보자.

 

"1부터 4까지 숫자 중에서 두 숫자를 선택해 합이 7 이상이 되는 조합을 찾으라"는 문제가 있다고 하자.

• 첫 숫자를 1로 선택 → 두 번째 숫자를 아무리 크게 선택해도 최대 합은 1+4=5이므로, 이미 목표인 7에 도달할 수 없다. 즉, 첫 숫자 1은 유망하지 않다 → 즉시 가지치기(pruning).
• 첫 숫자를 2로 선택 → 최대 합은 2+4=6으로 역시 목표(7) 미달 → 가지치기.
• 첫 숫자를 3으로 선택 → 두 번째 숫자 4를 선택하면 합이 7이 되므로 유망 → 계속 탐색하여 조건 충족.
• 첫 숫자를 4로 선택 → 이미 가장 큰 숫자이므로 더 선택 불가, 즉시 가지치기.
  
  

4) 유망함수는 그렇다면 누가 짜나?

지금까지 설명을 듣다 보면 자연스럽게 "유망함수는 어떻게 나오는가?"라는 의문이 들 수 있다. 유망함수가 알고리즘 안에 미리 포함된 것인지, 혹은 매번 문제를 풀 때마다 개발자가 직접 만드는 것인지 명확히 이해되지 않을 수도 있다.

 

유망함수는 문제를 해결하는 개발자가 직접 짠다. 즉, 백트래킹 알고리즘이란 기본 원리를 제공할 뿐, 어떤 경우에 탐색을 멈출지 판단하는 기준은 문제마다 다르기 때문에 일반적인 형태로 미리 준비되어 있을 수 없다.

 

예를 들어 위의 예시에서 “현재까지 고른 숫자들의 최대 가능 합이 목표치(7)에 미달하면 더 볼 가치가 없다”는 사실을 코드로 옮기면 다음과 같다.

 

TARGET = 7
nums   = [1, 2, 3, 4]

def promising(prefix, next_idx):
    """
    prefix : 지금까지 선택한 숫자들의 리스트
    next_idx : 아직 고르지 않은 숫자들의 첫 인덱스
    반환값  : True → 계속 탐색, False → 가지치기
    """
    # 아직 선택하지 않은 숫자 중 가장 큰 값
    if next_idx >= len(nums):
        max_remain = 0
    else:
        max_remain = nums[-1]                     # 정렬돼 있다고 가정

    # 지금까지 합 + 앞으로 가질 수 있는 최대값조차 TARGET에 못 미치면 비유망
    return sum(prefix) + max_remain >= TARGET

 

위 함수는 문제 구조를 분석한 사람이 직접 작성한 것이다.

 

즉,

1. 문제의 목표 (“합 ≥ 7”)와
2. 데이터의 특성 (“숫자가 1 ~ 4까지 오름차순”)을 이용해
3. “앞으로 얻을 수 있는 최댓값조차 기준 미달이면 중단”이라는 규칙을 만들었다.

유망함수를 설계할 때 실무에서 자주 쓰는 패턴을 간단히 살펴보면,

패턴	설명	사용 예
상한·하한(upper/lower bound)	부분 해 + 최적(또는 최악) 예상치를 계산해 기존 최적 해와 비교	배낭 문제, TSP
제약 조건 조기 검증	최종 해에 반드시 들어맞아야 하는 규칙을 부분 단계에서 미리 검사	스도쿠, 그래프 색칠
구조적 특성 활용	정렬·단조성·대칭성 등을 통해 불필요한 분기를 제거	조합 합계, N-Queen 대칭

위와 같이 “이 기준을 만족 못 하면 밑으로 100 개를 더 파도 소용없다” 라는 판단 근거를 스스로 정의해 주는 것이라 할 수 있다.

---

백트래킹의 동작 과정 : 비밀번호 찾기 예시

앞서 예시로 든 비밀번호 찾기를 예시로 백트래킹 동작을 살펴보자. 프루닝 기법도 포함하기 위해 다음과 같은 조건을 추가로 설정한다.

 

조건	설명	pruning 포인트
① 앞 두 자리 = 99	힌트로 미리 알려짐	깊이 0, 1에서 다른 숫자면 즉시 cut
② 네 자리 모두 서로 다른 숫자	중복 금지	이미 나온 숫자면 cut
③ 네 자리 합 = 22	(예시용 임의 제약)	부분 합 + 남은 자리*9 < 22 → cut

먼저 손으로 이 문제를 푼다고 상상해보면 다음과 같은 스텝을 따를 것이다. 

단계 1: 조건을 잘 읽고 이해한다.

• "앞 두 자리는 무조건 99야."
• "같은 숫자를 두 번 쓰면 안 된대."
• "네 자리 숫자의 합이 22여야 해."

단계 2: 앞 두 자리 숫자를 결정

"앞 두 자리는 무조건 99로 결정!" → 99__ __

• 현재 합계: 9 + 9 = 18

단계 3: 세 번째 숫자 고르기

"세 번째 자리 숫자는 9는 이미 사용했으니까 안 되고, 다른 숫자를 써야 해."

• 가능한 숫자: 0, 1, 2, 3, 4, 5, 6, 7, 8

하나씩 살펴보자.

• 0을 넣으면: 18 + 0 = 18. 아직 합이 모자라. 남은 한 자리로 22를 만들려면 4가 필요해. 가능성 O
• 1을 넣으면: 18 + 1 = 19. 남은 한 자리로 3이 필요해. 가능성 O
• 2를 넣으면: 18 + 2 = 20. 남은 한 자리로 2가 필요해. 가능성 O
• 3을 넣으면: 18 + 3 = 21. 남은 한 자리로 1이 필요해. 가능성 O
• 4를 넣으면: 18 + 4 = 22. 남은 한 자리에 0이 들어가면 조건 충족 가능성 O
• 5 이상을 넣으면: 합이 23 이상이 되어 조건 위반이므로 즉시 제외 (pruning)

가능성 있는 후보: 0, 1, 2, 3, 4

단계 4: 네 번째 숫자 고르기 (세 번째 숫자별로)

세 번째 숫자를 0부터 확인해 보자.

• 990__: 합계 18 → 마지막 자리 4 넣으면 합계 22 (가능)
• 991__: 합계 19 → 마지막 자리 3 넣으면 합계 22 (가능)
• 992__: 합계 20 → 마지막 자리 2 넣으면 합계 22 (가능)
• 993__: 합계 21 → 마지막 자리 1 넣으면 합계 22 (가능)
• 994__: 합계 22 → 마지막 자리 0 넣으면 합계 22 (가능)

모두 가능한 숫자 조합이다. 따라서 가능한 해답은:

• 9904, 9913, 9922, 9931, 9940 중에서 '숫자 중복 금지' 조건을 생각하면 9922는 숫자 2가 중복되어 제외 (pruning).

따라서, 최종 답안인 9904, 9913, 9931, 9940 네 개를 도출할 수 있다. 

<svg viewBox="0 0 1200 800" xmlns="http://www.w3.org/2000/svg">
  <!-- 배경 -->
  <rect width="1200" height="800" fill="#f8fafc"/>

  <!-- 제목 -->
  <text x="600" y="30" text-anchor="middle" font-size="20" font-weight="bold" fill="#1e293b">
    백트래킹: 비밀번호 찾기 (99__ , 서로 다른 숫자, 합=22)
  </text>

  <!-- 조건 설명 -->
  <g transform="translate(50, 50)">
    <rect x="0" y="0" width="300" height="80" fill="#e0f2fe" stroke="#0284c7" stroke-width="1" rx="5"/>
    <text x="10" y="20" font-size="12" font-weight="bold" fill="#0c4a6e">조건:</text>
    <text x="10" y="35" font-size="11" fill="#0c4a6e">① 앞 두 자리 = 99</text>
    <text x="10" y="50" font-size="11" fill="#0c4a6e">② 네 자리 모두 서로 다른 숫자</text>
    <text x="10" y="65" font-size="11" fill="#0c4a6e">③ 네 자리 합 = 22</text>
  </g>

  <!-- 루트 노드 -->
  <g id="root">
    <circle cx="600" cy="120" r="25" fill="#3b82f6" stroke="#1d4ed8" stroke-width="2"/>
    <text x="600" y="125" text-anchor="middle" font-size="12" font-weight="bold" fill="white">시작</text>
    <text x="600" y="150" text-anchor="middle" font-size="10" fill="#64748b">합: 0</text>
  </g>

  <!-- 1단계: 첫 번째 자리 (9) -->
  <g id="level1">
    <line x1="600" y1="145" x2="600" y2="200" stroke="#6b7280" stroke-width="2"/>
    <circle cx="600" cy="220" r="25" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="600" y="220" text-anchor="middle" font-size="14" font-weight="bold" fill="white">9</text>
    <text x="600" y="235" text-anchor="middle" font-size="12" fill="white">_ _ _</text>
    <text x="600" y="250" text-anchor="middle" font-size="10" fill="#64748b">합: 9</text>
  </g>

  <!-- 2단계: 두 번째 자리 (9) -->
  <g id="level2">
    <line x1="600" y1="245" x2="600" y2="300" stroke="#6b7280" stroke-width="2"/>
    <circle cx="600" cy="320" r="25" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="600" y="315" text-anchor="middle" font-size="12" font-weight="bold" fill="white">99</text>
    <text x="600" y="330" text-anchor="middle" font-size="12" fill="white">_ _</text>
    <text x="600" y="350" text-anchor="middle" font-size="10" fill="#64748b">합: 18</text>
  </g>

  <!-- 3단계: 세 번째 자리 후보들 -->
  <g id="level3">
    <!-- 연결선들 -->
    <line x1="600" y1="345" x2="200" y2="420" stroke="#6b7280" stroke-width="1"/>
    <line x1="600" y1="345" x2="350" y2="420" stroke="#6b7280" stroke-width="1"/>
    <line x1="600" y1="345" x2="500" y2="420" stroke="#6b7280" stroke-width="1"/>
    <line x1="600" y1="345" x2="650" y2="420" stroke="#6b7280" stroke-width="1"/>
    <line x1="600" y1="345" x2="800" y2="420" stroke="#6b7280" stroke-width="1"/>
    <line x1="600" y1="345" x2="950" y2="420" stroke="#6b7280" stroke-width="1"/>

    <!-- 유효한 후보들 (0,1,2,3,4) -->
    <circle cx="200" cy="420" r="20" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="200" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">0</text>
    <text x="200" y="445" text-anchor="middle" font-size="9" fill="#64748b">990_</text>
    <text x="200" y="455" text-anchor="middle" font-size="8" fill="#64748b">합:18</text>

    <circle cx="350" cy="420" r="20" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="350" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">1</text>
    <text x="350" y="445" text-anchor="middle" font-size="9" fill="#64748b">991_</text>
    <text x="350" y="455" text-anchor="middle" font-size="8" fill="#64748b">합:19</text>

    <circle cx="500" cy="420" r="20" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="500" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">2</text>
    <text x="500" y="445" text-anchor="middle" font-size="9" fill="#64748b">992_</text>
    <text x="500" y="455" text-anchor="middle" font-size="8" fill="#64748b">합:20</text>

    <circle cx="650" cy="420" r="20" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="650" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">3</text>
    <text x="650" y="445" text-anchor="middle" font-size="9" fill="#64748b">993_</text>
    <text x="650" y="455" text-anchor="middle" font-size="8" fill="#64748b">합:21</text>

    <circle cx="800" cy="420" r="20" fill="#10b981" stroke="#059669" stroke-width="2"/>
    <text x="800" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">4</text>
    <text x="800" y="445" text-anchor="middle" font-size="9" fill="#64748b">994_</text>
    <text x="800" y="455" text-anchor="middle" font-size="8" fill="#64748b">합:22</text>

    <!-- 프루닝된 후보들 (5이상) -->
    <circle cx="950" cy="420" r="20" fill="#ef4444" stroke="#dc2626" stroke-width="2"/>
    <text x="950" y="420" text-anchor="middle" font-size="12" font-weight="bold" fill="white">5+</text>
    <text x="950" y="445" text-anchor="middle" font-size="9" fill="#64748b">995+</text>
    <text x="950" y="455" text-anchor="middle" font-size="8" fill="#ef4444">합>22</text>

    <!-- 프루닝 표시 -->
    <line x1="935" y1="405" x2="965" y2="435" stroke="#dc2626" stroke-width="3"/>
    <line x1="965" y1="405" x2="935" y2="435" stroke="#dc2626" stroke-width="3"/>
    <text x="950" y="470" text-anchor="middle" font-size="10" font-weight="bold" fill="#dc2626">PRUNED</text>
  </g>

  <!-- 4단계: 네 번째 자리 후보들 (일부만 표시) -->
  <g id="level4">
    <!-- 연결선들 -->
    <line x1="200" y1="440" x2="150" y2="520" stroke="#6b7280" stroke-width="1"/>
    <line x1="350" y1="440" x2="300" y2="520" stroke="#6b7280" stroke-width="1"/>
    <line x1="500" y1="440" x2="450" y2="520" stroke="#6b7280" stroke-width="1"/>
    <line x1="650" y1="440" x2="600" y2="520" stroke="#6b7280" stroke-width="1"/>
    <line x1="800" y1="440" x2="750" y2="520" stroke="#6b7280" stroke-width="1"/>

    <!-- 최종 후보들 -->
    <circle cx="150" cy="520" r="18" fill="#f59e0b" stroke="#d97706" stroke-width="2"/>
    <text x="150" y="520" text-anchor="middle" font-size="11" font-weight="bold" fill="white">4</text>
    <text x="150" y="540" text-anchor="middle" font-size="8" fill="#64748b">9904</text>
    <text x="150" y="550" text-anchor="middle" font-size="8" fill="#64748b">합:22 ✓</text>

    <circle cx="300" cy="520" r="18" fill="#f59e0b" stroke="#d97706" stroke-width="2"/>
    <text x="300" y="520" text-anchor="middle" font-size="11" font-weight="bold" fill="white">3</text>
    <text x="300" y="540" text-anchor="middle" font-size="8" fill="#64748b">9913</text>
    <text x="300" y="550" text-anchor="middle" font-size="8" fill="#64748b">합:22 ✓</text>

    <circle cx="450" cy="520" r="18" fill="#f59e0b" stroke="#d97706" stroke-width="2"/>
    <text x="450" y="520" text-anchor="middle" font-size="11" font-weight="bold" fill="white">2</text>
    <text x="450" y="540" text-anchor="middle" font-size="8" fill="#64748b">9922</text>
    <text x="450" y="550" text-anchor="middle" font-size="8" fill="#ef4444">중복 ✗</text>

    <circle cx="600" cy="520" r="18" fill="#f59e0b" stroke="#d97706" stroke-width="2"/>
    <text x="600" y="520" text-anchor="middle" font-size="11" font-weight="bold" fill="white">1</text>
    <text x="600" y="540" text-anchor="middle" font-size="8" fill="#64748b">9931</text>
    <text x="600" y="550" text-anchor="middle" font-size="8" fill="#64748b">합:22 ✓</text>

    <circle cx="750" cy="520" r="18" fill="#f59e0b" stroke="#d97706" stroke-width="2"/>
    <text x="750" y="520" text-anchor="middle" font-size="11" font-weight="bold" fill="white">0</text>
    <text x="750" y="540" text-anchor="middle" font-size="8" fill="#64748b">9940</text>
    <text x="750" y="550" text-anchor="middle" font-size="8" fill="#64748b">합:22 ✓</text>

    <!-- 중복으로 인한 프루닝 표시 -->
    <line x1="435" y1="505" x2="465" y2="535" stroke="#dc2626" stroke-width="2"/>
    <line x1="465" y1="505" x2="435" y2="535" stroke="#dc2626" stroke-width="2"/>
  </g>

  <!-- 해답 표시 -->
  <g id="solutions">
    <rect x="50" y="600" width="1100" height="80" fill="#ecfdf5" stroke="#10b981" stroke-width="2" rx="10"/>
    <text x="80" y="625" font-size="14" font-weight="bold" fill="#047857">유효한 해답:</text>
    <text x="80" y="645" font-size="12" fill="#047857">9904 (9+9+0+4=22, 모두 다른 숫자)</text>
    <text x="80" y="660" font-size="12" fill="#047857">9913 (9+9+1+3=22, 모두 다른 숫자)</text>
    <text x="80" y="675" font-size="12" fill="#047857">9931 (9+9+3+1=22, 모두 다른 숫자)</text>
    <text x="500" y="645" font-size="12" fill="#047857">9940 (9+9+4+0=22, 모두 다른 숫자)</text>
  </g>

  <!-- 범례 -->
  <g id="legend" transform="translate(50, 720)">
    <text x="0" y="15" font-size="12" font-weight="bold" fill="#374151">범례:</text>

    <circle cx="70" cy="12" r="8" fill="#10b981"/>
    <text x="85" y="16" font-size="10" fill="#374151">유효한 노드</text>

    <circle cx="180" cy="12" r="8" fill="#ef4444"/>
    <line x1="175" y1="7" x2="185" y2="17" stroke="#fff" stroke-width="1"/>
    <line x1="185" y1="7" x2="175" y2="17" stroke="#fff" stroke-width="1"/>
    <text x="195" y="16" font-size="10" fill="#374151">프루닝된 노드</text>

    <circle cx="310" cy="12" r="8" fill="#f59e0b"/>
    <text x="325" y="16" font-size="10" fill="#374151">최종 후보</text>

    <rect x="420" y="5" width="15" height="15" fill="#ecfdf5" stroke="#10b981"/>
    <text x="445" y="16" font-size="10" fill="#374151">해답</text>
  </g>

  <!-- 프루닝 설명 -->
  <g transform="translate(900, 50)">
    <rect x="0" y="0" width="250" height="120" fill="#fef2f2" stroke="#ef4444" stroke-width="1" rx="5"/>
    <text x="10" y="20" font-size="12" font-weight="bold" fill="#dc2626">프루닝 조건:</text>
    <text x="10" y="40" font-size="10" fill="#dc2626">• 이미 사용된 숫자 (중복)</text>
    <text x="10" y="55" font-size="10" fill="#dc2626">• 부분합 + 남은자리×9 &lt; 22</text>
    <text x="10" y="70" font-size="10" fill="#dc2626">• 현재 합 &gt; 22</text>
    <text x="10" y="90" font-size="10" fill="#7c2d12">→ 더 이상 탐색하지 않고</text>
    <text x="10" y="105" font-size="10" fill="#7c2d12">   즉시 되돌아감</text>
  </g>
</svg>

 

3가지 프루닝 조건을 포함하고, 재귀 호출을 통해 백트래킹을 진행하는 함수는 다음과 같이 작성할 수 있다.

 

function findPassword(depth, currentPassword, currentSum, usedNumbers):
    if depth == 4:
        if currentSum == 22:
            add currentPassword to results
        return

    for number in 0 to 9:
        if depth < 2 and number != 9:
            continue // pruning (조건 ①)
        if number in usedNumbers:
            continue // pruning (조건 ②)
        if currentSum + number + (3 - depth) * 9 < 22:
            continue // pruning (조건 ③)
        if currentSum + number > 22:
            continue // pruning (합 초과)

        usedNumbers.add(number)
        findPassword(depth + 1, currentPassword + number, currentSum + number, usedNumbers)
        usedNumbers.remove(number)

// 초기 호출
results = []
findPassword(0, "", 0, empty set)
print(results)

 

• 조건 ① 프루닝: 처음 두 자리는 무조건 9여야 하므로 다른 숫자는 탐색할 가치가 없다고 판단하여 즉시 버림.
• 조건 ② 프루닝: 이미 사용된 숫자는 다시 사용하지 않도록 필터링.
• 조건 ③ 프루닝: 현재까지 합을 보고 남은 자리로 최대값을 더해도 목표에 도달하지 못하면 즉시 버림.

 

<svg viewBox="0 0 1400 600" xmlns="http://www.w3.org/2000/svg">
  <!-- 배경 -->
  <rect width="1400" height="600" fill="#f8fafc"/>
  
  <!-- 제목 -->
  <text x="700" y="30" text-anchor="middle" font-size="20" font-weight="bold" fill="#1e293b">
    백트래킹 스택 프레임 동작 메커니즘
  </text>
  
  <!-- 시간 단계 표시 -->
  <g id="timeline">
    <text x="50" y="70" font-size="14" font-weight="bold" fill="#374151">시간 흐름 →</text>
    <line x1="50" y1="80" x2="1350" y2="80" stroke="#d1d5db" stroke-width="2"/>
    
    <!-- 시간 단계들 -->
    <g id="time_steps">
      <text x="150" y="100" text-anchor="middle" font-size="12" fill="#6b7280">초기 호출</text>
      <text x="300" y="100" text-anchor="middle" font-size="12" fill="#6b7280">depth=0</text>
      <text x="450" y="100" text-anchor="middle" font-size="12" fill="#6b7280">depth=1</text>
      <text x="600" y="100" text-anchor="middle" font-size="12" fill="#6b7280">depth=2</text>
      <text x="750" y="100" text-anchor="middle" font-size="12" fill="#6b7280">depth=3</text>
      <text x="900" y="100" text-anchor="middle" font-size="12" fill="#6b7280">완료&반환</text>
      <text x="1050" y="100" text-anchor="middle" font-size="12" fill="#6b7280">백트래킹</text>
      <text x="1200" y="100" text-anchor="middle" font-size="12" fill="#6b7280">다른 경로</text>
    </g>
  </g>
  
  <!-- 스택 영역들 -->
  <g id="stack_areas">
    <!-- 초기 호출 -->
    <g id="initial_call" transform="translate(100, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      <text x="50" y="-10" text-anchor="middle" font-size="12" font-weight="bold" fill="#334155">스택</text>
      
      <!-- 스택 프레임 1 -->
      <rect x="10" y="350" width="80" height="40" fill="#3b82f6" stroke="#1d4ed8" stroke-width="1" rx="3"/>
      <text x="50" y="365" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="375" text-anchor="middle" font-size="8" fill="white">depth=0, ""</text>
      <text x="50" y="385" text-anchor="middle" font-size="8" fill="white">sum=0, used={}</text>
    </g>
    
    <!-- depth=0 처리 -->
    <g id="depth0" transform="translate(250, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 2 -->
      <rect x="10" y="300" width="80" height="40" fill="#10b981" stroke="#059669" stroke-width="1" rx="3"/>
      <text x="50" y="315" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="325" text-anchor="middle" font-size="8" fill="white">depth=1, "9"</text>
      <text x="50" y="335" text-anchor="middle" font-size="8" fill="white">sum=9, used={9}</text>
      
      <!-- 스택 프레임 1 -->
      <rect x="10" y="350" width="80" height="40" fill="#3b82f6" stroke="#1d4ed8" stroke-width="1" rx="3"/>
      <text x="50" y="365" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="375" text-anchor="middle" font-size="8" fill="white">depth=0, ""</text>
      <text x="50" y="385" text-anchor="middle" font-size="8" fill="white">sum=0, used={}</text>
      
      <!-- 호출 화살표 -->
      <path d="M 150 370 Q 200 350 250 320" fill="none" stroke="#059669" stroke-width="2" marker-end="url(#arrowhead)"/>
    </g>
    
    <!-- depth=1 처리 -->
    <g id="depth1" transform="translate(400, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 3 -->
      <rect x="10" y="250" width="80" height="40" fill="#f59e0b" stroke="#d97706" stroke-width="1" rx="3"/>
      <text x="50" y="265" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="275" text-anchor="middle" font-size="8" fill="white">depth=2, "99"</text>
      <text x="50" y="285" text-anchor="middle" font-size="8" fill="white">sum=18, used={9}</text>
      
      <!-- 스택 프레임 2 -->
      <rect x="10" y="300" width="80" height="40" fill="#10b981" stroke="#059669" stroke-width="1" rx="3"/>
      <text x="50" y="315" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="325" text-anchor="middle" font-size="8" fill="white">depth=1, "9"</text>
      <text x="50" y="335" text-anchor="middle" font-size="8" fill="white">sum=9, used={9}</text>
      
      <!-- 스택 프레임 1 -->
      <rect x="10" y="350" width="80" height="40" fill="#3b82f6" stroke="#1d4ed8" stroke-width="1" rx="3"/>
      <text x="50" y="365" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="375" text-anchor="middle" font-size="8" fill="white">depth=0, ""</text>
      <text x="50" y="385" text-anchor="middle" font-size="8" fill="white">sum=0, used={}</text>
      
      <!-- 호출 화살표 -->
      <path d="M 300 320 Q 350 300 400 270" fill="none" stroke="#d97706" stroke-width="2" marker-end="url(#arrowhead)"/>
    </g>
    
    <!-- depth=2 처리 -->
    <g id="depth2" transform="translate(550, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 4 -->
      <rect x="10" y="200" width="80" height="40" fill="#8b5cf6" stroke="#7c3aed" stroke-width="1" rx="3"/>
      <text x="50" y="215" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="225" text-anchor="middle" font-size="8" fill="white">depth=3, "990"</text>
      <text x="50" y="235" text-anchor="middle" font-size="8" fill="white">sum=18, used={9,0}</text>
      
      <!-- 스택 프레임 3 -->
      <rect x="10" y="250" width="80" height="40" fill="#f59e0b" stroke="#d97706" stroke-width="1" rx="3"/>
      <text x="50" y="265" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="275" text-anchor="middle" font-size="8" fill="white">depth=2, "99"</text>
      <text x="50" y="285" text-anchor="middle" font-size="8" fill="white">sum=18, used={9}</text>
      
      <!-- 스택 프레임 2 -->
      <rect x="10" y="300" width="80" height="40" fill="#10b981" stroke="#059669" stroke-width="1" rx="3"/>
      <text x="50" y="315" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="325" text-anchor="middle" font-size="8" fill="white">depth=1, "9"</text>
      <text x="50" y="335" text-anchor="middle" font-size="8" fill="white">sum=9, used={9}</text>
      
      <!-- 스택 프레임 1 -->
      <rect x="10" y="350" width="80" height="40" fill="#3b82f6" stroke="#1d4ed8" stroke-width="1" rx="3"/>
      <text x="50" y="365" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="375" text-anchor="middle" font-size="8" fill="white">depth=0, ""</text>
      <text x="50" y="385" text-anchor="middle" font-size="8" fill="white">sum=0, used={}</text>
      
      <!-- 호출 화살표 -->
      <path d="M 450 270 Q 500 250 550 220" fill="none" stroke="#7c3aed" stroke-width="2" marker-end="url(#arrowhead)"/>
    </g>
    
    <!-- depth=3 처리 (완료) -->
    <g id="depth3" transform="translate(700, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 5 (해답 발견) -->
      <rect x="10" y="150" width="80" height="40" fill="#ef4444" stroke="#dc2626" stroke-width="1" rx="3"/>
      <text x="50" y="165" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="175" text-anchor="middle" font-size="8" fill="white">depth=4, "9904"</text>
      <text x="50" y="185" text-anchor="middle" font-size="8" fill="white">sum=22 ✓</text>
      
      <!-- 스택 프레임 4 -->
      <rect x="10" y="200" width="80" height="40" fill="#8b5cf6" stroke="#7c3aed" stroke-width="1" rx="3"/>
      <text x="50" y="215" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="225" text-anchor="middle" font-size="8" fill="white">depth=3, "990"</text>
      <text x="50" y="235" text-anchor="middle" font-size="8" fill="white">sum=18, used={9,0}</text>
      
      <!-- 스택 프레임 3 -->
      <rect x="10" y="250" width="80" height="40" fill="#f59e0b" stroke="#d97706" stroke-width="1" rx="3"/>
      <text x="50" y="265" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="275" text-anchor="middle" font-size="8" fill="white">depth=2, "99"</text>
      <text x="50" y="285" text-anchor="middle" font-size="8" fill="white">sum=18, used={9}</text>
      
      <!-- 스택 프레임 2 -->
      <rect x="10" y="300" width="80" height="40" fill="#10b981" stroke="#059669" stroke-width="1" rx="3"/>
      <text x="50" y="315" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="325" text-anchor="middle" font-size="8" fill="white">depth=1, "9"</text>
      <text x="50" y="335" text-anchor="middle" font-size="8" fill="white">sum=9, used={9}</text>
      
      <!-- 스택 프레임 1 -->
      <rect x="10" y="350" width="80" height="40" fill="#3b82f6" stroke="#1d4ed8" stroke-width="1" rx="3"/>
      <text x="50" y="365" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="375" text-anchor="middle" font-size="8" fill="white">depth=0, ""</text>
      <text x="50" y="385" text-anchor="middle" font-size="8" fill="white">sum=0, used={}</text>
      
      <!-- 호출 화살표 -->
      <path d="M 600 220 Q 650 200 700 170" fill="none" stroke="#dc2626" stroke-width="2" marker-end="url(#arrowhead)"/>
      
      <!-- 해답 저장 표시 -->
      <rect x="10" y="100" width="80" height="30" fill="#22c55e" stroke="#16a34a" stroke-width="1" rx="3"/>
      <text x="50" y="112" text-anchor="middle" font-size="8" fill="white">results.add</text>
      <text x="50" y="122" text-anchor="middle" font-size="8" fill="white">("9904")</text>
    </g>
    
    <!-- 반환 과정 -->
    <g id="return_process" transform="translate(850, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 4 (반환됨) -->
      <rect x="10" y="200" width="80" height="40" fill="#8b5cf6" stroke="#7c3aed" stroke-width="1" rx="3" opacity="0.5"/>
      <text x="50" y="215" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="225" text-anchor="middle" font-size="8" fill="white">(반환됨)</text>
      
      <!-- 스택 프레임 3 -->
      <rect x="10" y="250" width="80" height="40" fill="#f59e0b" stroke="#d97706" stroke-width="1" rx="3"/>
      <text x="50" y="265" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="275" text-anchor="middle" font-size="8" fill="white">depth=2, "99"</text>
      <text x="50" y="285" text-anchor="middle" font-size="8" fill="white">다음 숫자 시도</text>
      
      <!-- 반환 화살표 -->
      <path d="M 750 170 Q 800 190 850 220" fill="none" stroke="#ef4444" stroke-width="2" stroke-dasharray="5,5" marker-end="url(#arrowhead)"/>
      <text x="800" y="185" text-anchor="middle" font-size="10" fill="#ef4444">return</text>
    </g>
    
    <!-- 백트래킹 과정 -->
    <g id="backtrack_process" transform="translate(1000, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 스택 프레임 4 (새로운 시도) -->
      <rect x="10" y="200" width="80" height="40" fill="#8b5cf6" stroke="#7c3aed" stroke-width="1" rx="3"/>
      <text x="50" y="215" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="225" text-anchor="middle" font-size="8" fill="white">depth=3, "991"</text>
      <text x="50" y="235" text-anchor="middle" font-size="8" fill="white">sum=19, used={9,1}</text>
      
      <!-- 스택 프레임 3 -->
      <rect x="10" y="250" width="80" height="40" fill="#f59e0b" stroke="#d97706" stroke-width="1" rx="3"/>
      <text x="50" y="265" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="275" text-anchor="middle" font-size="8" fill="white">depth=2, "99"</text>
      <text x="50" y="285" text-anchor="middle" font-size="8" fill="white">숫자 1 시도</text>
      
      <!-- 백트래킹 화살표 -->
      <path d="M 900 270 Q 950 250 1000 220" fill="none" stroke="#7c3aed" stroke-width="2" marker-end="url(#arrowhead)"/>
    </g>
    
    <!-- 다른 경로 탐색 -->
    <g id="other_path" transform="translate(1150, 120)">
      <rect x="0" y="0" width="100" height="400" fill="#f1f5f9" stroke="#cbd5e1" stroke-width="2"/>
      
      <!-- 계속된 탐색 -->
      <rect x="10" y="150" width="80" height="40" fill="#ef4444" stroke="#dc2626" stroke-width="1" rx="3"/>
      <text x="50" y="165" text-anchor="middle" font-size="9" fill="white">findPassword</text>
      <text x="50" y="175" text-anchor="middle" font-size="8" fill="white">depth=4, "9913"</text>
      <text x="50" y="185" text-anchor="middle" font-size="8" fill="white">sum=22 ✓</text>
      
      <!-- 해답 저장 표시 -->
      <rect x="10" y="100" width="80" height="30" fill="#22c55e" stroke="#16a34a" stroke-width="1" rx="3"/>
      <text x="50" y="112" text-anchor="middle" font-size="8" fill="white">results.add</text>
      <text x="50" y="122" text-anchor="middle" font-size="8" fill="white">("9913")</text>
    </g>
  </g>
  
  
  <!-- 화살표 정의 -->
  <defs>
    <marker id="arrowhead" markerWidth="10" markerHeight="7" refX="10" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#059669"/>
    </marker>
  </defs>
</svg>

 

유망함수는 매 재귀 호출마다 네 가지 규칙으로 “계속 탐색할 가치가 있는지”를 즉시 평가한다.

 

탈락한 분기는 가지치기로 스택에 쌓이지 않고 잘려나가 탐색 트리가 기하급수적으로 축소된다.

 

 

---