백트래킹(Backtracking) - 조합, 순열, N-Queen

백트래킹이란?

Backtracking은

"모든 가능성을 시도하되, 가능성이 없는 가지는 빠르게 포기하는 전략" 입니다.
DFS기반으로 경로를 탐색하다가 
조건을 만족하지 않으면 되돌아가서(Backtrack) 다시 다른 경로를 시도는 하는 방식입니다.

---

백트래킹이 필요한 문제의 특징

• 해가 여러 개 존재 (조합, 순열, 경로 등)
• 모든 경우를 탐색해야 하되, 중간에 가지치기(pruning) 가능
• 대표 키워드:
  • "모든 경우의 수"
  • "최대/최소"
  • "가능한 배치"
  • "n개의 원소를 이용해 조건 만족하는 케이스 찾기"

---

DFS와 백트래킹의 차이

항목	DFS	백트래킹
목적	그래프 전체 탐색	조건 만족하는 해 찾기
되돌아오기	단순 순회	조건 만족 못하면 되돌아감 (Pruning)
사용 구조	재귀/스택	재귀 + 조건 분기 + 가지치

---

1: 순열 (Permutation)

문제: 1부터 N까지의 숫자 중에서 모든 순열을 출력하라

 

핵심 로직

• 방문한 수를 제외한 모든 수에 대해 재귀 호출
• 백트래킹: 현재 경로에서 visited를 해제하며 되돌아옴

def permute(nums):
    result = []
    visited = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            visited[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            visited[i] = False

    backtrack([])
    return result

---

2: 조합 (Combination)

문제: 1부터 N까지의 수 중에서 K개를 고르는 모든 조합

def combine(n, k):
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

비교: 순열 vs 조합

항목	순열	조합
순서	중요	무관
visited 사용	필요	불필요 (start index 사용)
출력 예	[1, 2], [2, 1]	[1, 2]

---

3: N-Queen 문제

문제: N x N 체스판 위에 서로 공격하지 않도록 N개의 퀸을 배치하라

def solve_n_queens(n):
    result = []

    def backtrack(row, cols, diag1, diag2, path):
        if row == n:
            result.append(path[:])
            return
        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)
            board_row = '.' * col + 'Q' + '.' * (n - col - 1)
            backtrack(row + 1, cols, diag1, diag2, path + [board_row])
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0, set(), set(), set(), [])
    return result

---

가지치기(Pruning)의 핵심

"이 경로는 정답이 될 수 없다"는 것을 빨리 파악하고 탐색 중단

Pruning 기법 예시

• 조건 위배 즉시 return
• 중복 제거 (조합 vs 순열)
• • 정렬 후 조건 만족 여부 확인 (ex: 조합합 > target)

---

패턴 요약

패턴	특징
조합	start index 증가, visited 필요 없음
순열	visited 필요, 모든 경우
중복 순열	visited 없이 모든 선택 가능
조건 기반 탐색	경로 조건 검사 + pruning
제약 충족 탐	ex: Sudoku, N-Queen 등

---

결론

백트래킹은 단순한 완전 탐색을 "영리하게" 만드는 전략입니다.
모든 경우를 보되, 가지 않아도 될 길을 빠르게 포기하는 똑똑한 탐색 방식입니다.

 

조건과 상태 정의만 잘 해두면 

조합/순열/조건탐색/N-Queen/Sudoku/암호찾기 등 거의 모든 경우의 수 문제에 강력하게 적용됩니다.

감사합니다.