[JAVA] 백트래킹(Backtracking) | 개념, 동작 흐름, 예시 ⭕️

프로그래머스 [피로도] 문제를 풀며 배운 백트래킹에 대해서 정리한 글입니다. 

🔙 백트래킹(Backtracking) 

---

📌  백트래킹이란?

문제를 해결하기 위해 가능한 모든 후보 해를 순차적으로 시도하면서,

조건에 맞지 않으면 그 지점에서 되돌아가서 다른 경로를 탐색하는 기법 또는 조기에 가지치기(Pruning) 하는 기법

즉, DFS 기반의 조건부 완전 탐색

 

 

✅  핵심 개념 요약

탐색 방식	깊이 우선 탐색 (DFS 기반)
사용 목적	모든 경우의 수(조합, 순열, 경로 탐색 등)를 시도하면서 조건에 맞는 정답만 걸러냄
핵심 동작	“선택 → 탐색 → 백트래킹(원복)”
사용 구조	재귀 함수를 사용하여 상태를 저장하고 복원
장점	완전탐색보다 효율적: 가지치기로 불필요한 경로를 생략

 

💡 백트래킹 동작 흐름

void backtrack(상태) {
    if (종료 조건 만족) {
        결과 처리;
        return;
    }

    for (모든 가능한 선택지 s) {
        if (조건에 맞는 선택 s) {
            선택 수행;
            backtrack(변화된 상태);
            선택 원복; // 백트래킹 핵심
        }
    }
}

 

🧠 핵심 키워드 4가지

상태	현재까지 선택한 경로 (예: 현재까지 고른 숫자들)
선택	다음에 어떤 선택지를 사용할지 결정 (for 루프)
조건	선택이 유효한지 검사 (if 문)
백트래킹	선택 후 재귀 → 다시 돌아올 때 선택 원복

 

 

 

🔍 예제 1️⃣ :  1~3의 순열 (중복 없이)

1, 2, 3 숫자 중 중복 없이 모든 순열 출력

import java.util.*;

public class PermutationBacktrack {
    public static void main(String[] args) {
        boolean[] visited = new boolean[4]; // 1~3 사용
        List<Integer> path = new ArrayList<>();
        backtrack(path, visited);
    }

    static void backtrack(List<Integer> path, boolean[] visited) {
        if (path.size() == 3) {
            System.out.println(path);
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (!visited[i]) { // 조건 검사
                visited[i] = true;         // 선택
                path.add(i);               // 상태 변화

                backtrack(path, visited);  // 다음 단계로

                path.remove(path.size() - 1); // 상태 복원 (백트래킹)
                visited[i] = false;           // 선택 복원
            }
        }
    }
}

 

출력 :
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

 

 

✨ 백트래킹의 흐름 시각화 (DFS)

[]
├─ [1]
│  ├─ [1,2]
│  │  └─ [1,2,3] ✅
│  └─ [1,3]
│     └─ [1,3,2] ✅
├─ [2]
│  ├─ [2,1]
│  │  └─ [2,1,3] ✅
│  └─ [2,3]
│     └─ [2,3,1] ✅
└─ [3]
   ├─ [3,1]
   │  └─ [3,1,2] ✅
   └─ [3,2]
      └─ [3,2,1] ✅

 

 

🔍 예제 2️⃣ :  프로그래머스 - 피로도 

https://mang-kko.tistory.com/100

[프로그래머스|JAVA] 피로도 | 완전탐색 dfs | 백트래킹

 

 

🧠 백트래킹 vs DFS 차이?

	DFS	백트래킹
목적	모든 경로 탐색	정답 조건만 탐색
가지치기	없음	조건 검사 + 가지치기
종료 조건	일반적으로 노드 끝까지	조건을 만족하는 경우만 리턴

 

 

---

 

 

📍 백트래킹은 자바에서 DFS + 조건 + 복원을 조합해서 가능한 모든 선택지를 안전하게 탐색할 수 있게 해주는 강력한 기법으로 앞으로 문제를 해결할 때 아래의 구조만 잘기억했다 활용하면 될 것 같다.

for (선택지) {
    if (조건 만족) {
        선택
        재귀
        원복 (백트래킹)
    }
}