백준 / 2529 / 백트랙킹

https://www.acmicpc.net/problem/2529

🚀 백트래킹을 코딩할 때, 머릿속에서 과정들을 상상하는 방법

재귀 호출과 백트래킹 과정 머릿속에서 생각하기가 어렵다면... 

---

🧠 1️⃣ "트리(Tree) 구조로 상상하기"

모든 선택지를 하나씩 탐색하는 트리(Tree) 구조라고 생각하기

예를 들어, 2 < > 문제
즉, 숫자를 하나 선택할 때마다 "현재 노드에서 가지가 뻗어나가는" 것을 상상

🔹 상상하는 트리 구조

              (빈 값)
            /  |  |  |  |  |  |  |  |  |  
          0    1  2  3  4  5  6  7  8  9   → (X1 선택)
        /  |  
      01   02  ...                        → (X2 선택)
     /  |
  010   012  ...                          → (X3 선택)

✅ 이 트리에서 DFS(깊이 우선 탐색)를 하면서 숫자를 탐색하는 것이 백트래킹!

---

🧠 2️⃣ "손으로 직접 써보면서 정리하기" ✍

코드를 머리로만 생각하면 쉽게 꼬이기 때문에, 백트래킹 과정을 직접 적어보는 것이 중요!

📌 예제 (2 < >)를 직접 써보자.

index = 0, num = ""
선택할 수 있는 숫자 = {0~9}

1️⃣ index = 0 → "0" 선택  (0 < X2 만족해야 함)
2️⃣ index = 1 → "1" 선택  ("0 < 1" 만족)
3️⃣ index = 2 → "0" 선택  ("1 > 0" 만족)  → 저장 ("010")

🔙 백트래킹 (이전 숫자로 돌아감)
2️⃣ index = 1 → "2" 선택 ("0 < 2" 만족)
3️⃣ index = 2 → "1" 선택 ("2 > 1" 만족)  → 저장 ("021")

🔙 백트래킹 반복하여 "210" 찾기

✅ 손으로 한 번 써보면 "아! 이렇게 경우의 수가 돌아가는구나"를 직관적으로 이해할 수 있음.

---

🧠 3️⃣ "코드를 종이에 트레이싱(Tracing) 해보기"

📌 트레이싱할 코드 (재귀 호출 과정 보기)

#include <iostream>
using namespace std;

void FindNumbers(int index, string num) 
{
    cout << "index: " << index << ", num: " << num << endl;

    if (index == 3) 
    {
        cout << "✅ 저장됨: " << num << endl;
        return;
    }

    for (int i = 0; i <= 2; i++) 
    {
        cout << "🔄 i = " << i << " 선택 시도" << endl;
        FindNumbers(index + 1, num + (char)(i + '0'));
        cout << "🔙 백트래킹: i = " << i << " 제거 후 돌아감" << endl;
    }
}

int main() 
{
    FindNumbers(0, "");
    return 0;
}

✅ 이 코드를 실행하면서 직접 cout 출력을 확인해보면, 백트래킹 과정이 머릿속에서 정리됨.
✅ 코드가 실행되면서 "🔄 선택" → "✅ 저장" → "🔙 백트래킹"이 반복되는 것을 직접 확인해봐야 했다. ㅜㅡ

---

🧠 4️⃣ "백트래킹 코드 작성 시 3단계로 나누기"

✅ 백트래킹 코드의 핵심 3단계

void Backtracking(int index, string num) 
{
    // 1️⃣ 종료 조건
    if (index == 원하는 길이) 
    {
        결과 저장;
        return;
    }

    // 2️⃣ 가능한 숫자 탐색 (for문)
    for (int i = 0; i <= 9; i++) 
    {
        if (조건 만족하면) 
        {
            // 3️⃣ 선택 → 탐색 → 백트래킹
            방문 체크;
            Backtracking(index + 1, num + i);
            방문 해제 (백트래킹);
        }
    }
}

 

---

📌 결론: 백트래킹을 코딩할 때 머리에서 상상하는 방법

1️⃣ 트리(Tree) 구조로 상상하면서 "어떤 가지를 탐색할 것인가"를 생각하자.
2️⃣ 손으로 직접 경우의 수를 써보고, 어떤 경로로 탐색하는지 정리하자.
3️⃣ 코드를 실행하면서 cout으로 출력해 백트래킹 과정이 어떻게 돌아가는지 확인하자.
4️⃣ 백트래킹 코드의 "1️⃣ 종료 조건 → 2️⃣ 탐색 → 3️⃣ 백트래킹" 흐름을 이해하자.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int k;
char inequality[10]; 
bool visited[10];    
string minResult = "9999999999", maxResult = "0000000000"; 

// 부등호 조건을 만족하는지 확인하는 함수
bool check(char op, char a, char b) 
{
    if (op == '<') return a < b;
    if (op == '>') return a > b;
    return false;
}


void dfs(int idx, string num) 
{
    if (idx == k + 1) 
    {
        minResult = min(minResult, num);
        maxResult = max(maxResult, num);
        return;
    }

    for (int i = 0; i <= 9; i++) 
    {
        if (!visited[i]) 
        {
            if (idx == 0 || check(inequality[idx - 1], num.back(), i + '0')) 
            {
                visited[i] = true;
                dfs(idx + 1, num + (char)(i + '0'));
                visited[i] = false;
            }
        }
    }
}

int main() 
{
    
    cin >> k;
    for (int i = 0; i < k; i++) 
    {
        cin >> inequality[i];
    }

    
    dfs(0, "");

    
    cout << maxResult << endl;
    cout << minResult << endl;

    return 0;
}