[BFS/DFS] 백트래킹 4가지 유형

✅ DFS가 최적해를 찾는 4가지 유형 구현

DFS는 최적해를 찾는 문제에서 자주 활용되며,
특히 백트래킹(Pruning)과 함께 사용하면 불필요한 탐색을 줄일 수 있음.

아래 4가지 유형을 세부 설명과 함께 C++ 코드로 정리하겠습니다.

---

1️⃣ N-Queens 문제 (백트래킹 활용)

📌 문제 개요

• N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법의 수를 찾는 문제
• 한 행에 하나의 퀸을 놓으면서 조건을 만족하는지 확인

📌 최적해 찾는 방식

• DFS + 백트래킹을 활용
• 퀸을 놓을 때마다 유효한 위치인지 확인(Pruning)
• 가능한 경우만 탐색하며 최적해를 찾음

📌 C++ 코드

#include <iostream>
#include <vector>
using namespace std;

int N, solutions = 0;
vector<int> board;  // board[i] = j → i번째 행에 j번째 열에 퀸을 배치

// 퀸을 놓을 수 있는지 체크
bool isSafe(int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (board[i] == col || abs(board[i] - col) == row - i) {
            return false;  // 같은 열 또는 대각선에 위치하면 불가능
        }
    }
    return true;
}

// 백트래킹을 활용한 DFS 탐색
void solve(int row) {
    if (row == N) {  // 모든 행에 퀸을 배치 완료
        solutions++;
        return;
    }

    for (int col = 0; col < N; ++col) {
        if (isSafe(row, col)) {
            board[row] = col;
            solve(row + 1);
        }
    }
}

int main() {
    cout << "Enter N: ";
    cin >> N;
    board.resize(N);
    
    solve(0);
    cout << "Total solutions: " << solutions << endl;
    return 0;
}

🏆 DFS 활용 포인트

✅ 가능한 경우만 탐색하여 불필요한 연산을 줄임
✅ 백트래킹(Pruning)으로 가지치기
✅ isSafe() 함수로 대각선, 같은 열 체크하여 탐색량 감소

 

 

✅ 최종 출력값이 놓을수 있는 경우의 총 수이기때문에 굳이 경로를 기억해 놓을 필요가 없음.

✅ 따라서, 경로 변수를 pop 하지 않고 덮어씀.

 

✅ 행을 하나씩 증가하면서 확인하기 때문에, 행이 겹칠일이 없음.

✅ 따라서, visited 변수를 사용하지 않음.

---

2️⃣ 부분집합 합 문제 (Subset Sum Problem)

📌 문제 개요

• 주어진 숫자 배열에서 합이 target과 같은 부분집합이 존재하는지 확인
• 모든 부분집합을 탐색해야 하므로 DFS 사용
• 불필요한 탐색을 줄이기 위해 백트래킹 사용

📌 최적해 찾는 방식

• DFS로 각 원소를 포함하는 경우와 포함하지 않는 경우로 분기
• 현재 합이 target을 초과하면 백트래킹(Pruning)

📌 C++ 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> nums;
int target;

bool subsetSum(int index, int currentSum) {
    if (currentSum == target) return true;  // 목표 합 도달 시 성공
    if (index >= nums.size() || currentSum > target) return false;  // 백트래킹

    // 현재 원소를 포함하는 경우 OR 포함하지 않는 경우
    return subsetSum(index + 1, currentSum + nums[index]) || 
           subsetSum(index + 1, currentSum);
}

int main() {
    int n;
    cout << "Enter number of elements: ";
    cin >> n;

    nums.resize(n);
    cout << "Enter elements: ";
    for (int &num : nums) cin >> num;

    cout << "Enter target sum: ";
    cin >> target;

    if (subsetSum(0, 0)) cout << "Subset with given sum exists!" << endl;
    else cout << "No subset with given sum found." << endl;

    return 0;
}

🏆 DFS 활용 포인트

✅ 모든 부분집합을 탐색해야 하므로 DFS 사용
✅ 가지치기(Pruning) → 현재 합이 target을 초과하면 즉시 종료

 

✅ 최종 출력값이 놓을수 있는 경우의 총 수이기때문에 굳이 경로를 기억해 놓을 필요가 없음.

✅ 따라서, 경로 변수를 pop 하지 않음.

---

 

3️⃣ 트리에서 최대 경로 합 찾기 (Maximum Path Sum in Tree)

📌 문제 개요

• 루트에서 리프까지의 경로 중 최대 합을 찾는 문제
• BFS보다 DFS가 적합 (각 경로별로 값을 유지하며 탐색 가능)

📌 최적해 찾는 방식

• DFS를 사용하여 현재 노드까지의 합을 유지하면서 탐색
• 최대 값을 계속 갱신

📌 C++ 코드

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// DFS 탐색
int maxPathSum(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->val;

    return root->val + max(maxPathSum(root->left), maxPathSum(root->right));
}

int main() {
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(40);
    root->left->right = new TreeNode(50);

    cout << "Max path sum: " << maxPathSum(root) << endl;
    return 0;
}

🏆 DFS 활용 포인트

✅ 각 경로별로 값을 유지하며 탐색해야 하므로 DFS 적합
✅ 재귀 호출을 통해 최대값을 지속적으로 갱신

---

🔥 정리

문제 유형DFS가 적합한 이유BFS가 부적합한 이유

N-Queens	백트래킹으로 불필요한 탐색 제거 가능	모든 경우를 탐색하면 비효율적
부분집합 합	특정 조건을 만족하는 부분집합 탐색 가능	모든 경우를 한꺼번에 탐색 어려움
동전 조합	선택/미선택으로 분기 가능	경우의 수가 너무 많아짐
트리 최대 경로 합	현재까지의 합을 유지하며 탐색 가능	모든 경로를 기억해야 하므로 비효율적

✅ DFS는 "최단 거리"보다는 "최적 조합, 최대/최소값 찾기"에 적합! 🚀