백트래킹(Backtracking) 알고리즘 - 가지치기의 중요성(개념,원리,시간복잡도, C언어,Java,Python 예시코드)

백트래킹 알고리즘

 

 

백트래킹(Backtracking)은 탐색 알고리즘의 한 종류로, 코딩테스트 문제 해결에서 매우 중요한 역할을 합니다. 오늘은 백트래킹의 개념, 동작 원리, 시간복잡도, 장단점, 대표 문제들과 함께 C, Java, Python 예제 코드를 정리하겠습니다.

---

 

1. 백트래킹(Backtracking) 알고리즘이란?

백트래킹은 가능한 모든 경우를 탐색하면서도, 조건에 맞지 않는 경로는 탐색을 중단(가지치기)하는 알고리즘입니다. 불필요한 탐색을 줄이기 때문에 브루트포스보다 더 효율적입니다.

핵심 원리:

• 유망(promising)한 경로만 탐색.
• 조건을 만족하지 않으면 되돌아가서(Backtrack) 다른 경로 탐색.

적용 분야:

• 순열, 조합 문제
• 그래프 탐색 문제
• 퍼즐 문제(N-Queen, Sudoku 등)

---

 

반응형

2. 백트래킹 동작 원리

백트래킹은 다음과 같은 과정으로 동작합니다:

1. 탐색 시작: 가능한 경로를 하나씩 시도.
2. 조건 만족여부 판단: 현재 상태가 조건을 만족하는지 확인.
3. 가지치기: 조건을 만족하지 않으면 해당 경로를 포기하고 돌아감. 조건을 만족하면 계속 해당 경로로 깊게 나아감.
4. 정답 도출: 조건을 만족하는 경우 결과를 저장.

 

3. 백트래킹 구현 방식

• 재귀 방식: 대부분의 백트래킹 문제는 재귀적으로 해결.
• 반복문 + 스택: 재귀를 사용하지 않고 스택을 활용한 구현도 가능.

예시: N-Queens 문제

• 체스판에서 N개의 퀸이 서로 공격하지 않도록 배치하는 모든 경우를 탐색.

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True

def n_queens(n, row=0, board=[]):
    if row == n:
        print("Solution:", board)
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            n_queens(n, row + 1, board + [col])

n_queens(4)

---

 

4. 백트래킹의 시간복잡도

백트래킹의 시간복잡도는 문제의 크기와 가지치기의 효과에 따라 달라집니다.

 

최악의 경우: O(b^d)

• b: 각 단계에서 가능한 선택지 수
• d: 탐색의 깊이

가지치기 효과:

효과적으로 가지치기를 할 경우, 실제 탐색 시간은 훨씬 줄어듭니다.

---

 

5. 백트래킹의 장단점

장점:

1. 효율적인 탐색: 유망하지 않은 경로를 제거하여 탐색량 감소.
2. 모든 경우를 고려: 최적해를 보장.
3. 다양한 문제 적용 가능: 순열, 조합, 퍼즐 등 다양한 문제에 적합.

단점:

1. 최악의 경우 비효율적: 가지치기가 실패하면 브루트포스처럼 동작.
2. 구현 복잡성: 재귀와 조건 처리가 까다로울 수 있음.

---

 

6. 백트래킹 대표 문제

문제 1: N-Queens 문제

• n × n 체스판에서 퀸이 서로 공격하지 않도록 배치.

문제 2: Sudoku 풀기

• 9 × 9 스도쿠 퍼즐을 조건에 맞게 완성.

문제 3: 부분집합의 합

• 주어진 배열에서 합이 특정 값이 되는 부분집합 찾기.

---

 

7. 코드 예시

C 코드 예시: N-Queens 문제

#include <stdio.h>
#include <stdbool.h>

#define N 8

bool isSafe(int board[N][N], int row, int col) {
    for (int i = 0; i < row; i++)
        if (board[i][col]) return false;

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return false;

    for (int i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j]) return false;

    return true;
}

void solveNQueens(int board[N][N], int row) {
    if (row == N) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                printf("%d ", board[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }

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

int main() {
    int board[N][N] = {0};
    solveNQueens(board, 0);
    return 0;
}

---

 

Java 코드 예시: 부분집합의 합

import java.util.*;

public class SubsetSum {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 5;
        findSubsets(nums, target, new ArrayList<>(), 0);
    }

    public static void findSubsets(int[] nums, int target, List<Integer> current, int index) {
        if (target == 0) {
            System.out.println(current);
            return;
        }
        if (index >= nums.length || target < 0) return;

        current.add(nums[index]);
        findSubsets(nums, target - nums[index], current, index + 1);
        current.remove(current.size() - 1);
        findSubsets(nums, target, current, index + 1);
    }
}

---

 

Python 코드 예시: Sudoku 풀기

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num or board[i][col] == num or \
           board[row//3*3 + i//3][col//3*3 + i%3] == num:
            return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0
                return False
    return True

board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)
for row in board:
    print(row)

---

 

백트래킹 알고리즘은 탐색 문제의 핵심 기법으로, 효율성과 정확성을 동시에 제공합니다. 다만, 조건 설정과 가지치기 구현이 중요하니 충분한 연습이 필요합니다.

 

 

읽어보면 좋은 글

참고) 백트래킹, 브루트포스, dfs 비교 

2024.12.20 - [알고리즘] - 브루트포스, DFS, 백트래킹 차이점 정리

브루트포스, DFS, 백트래킹 차이점 정리

 

참고) 메모이제이션을 통한 백트래킹 성능 개선

2024.12.21 - [알고리즘] - 메모이제이션(Memoization) 적용을 통한 성능 개선 (2) - 백트래킹