백트래킹

 

📍 정의 및 특징

브루트포스에서 가지치기 진행

- DFS의 한 종류 (재귀)

- N이 최대 10으로 작을 경우, 백트래킹 가능

 

#가지치기 #DFS #재귀

 

 

📍 시간 복잡도

▷ 중복 가능한 경우

  ⋄ N^N
  ⋄ N = 8 까지 가능

 

▷ 중복 불가한 경우

  ⋄ N !
  ⋄ N = 10 까지 가능

 

 

📍 필요 변수

✔ 방문 여부 확인 배열 : boolean[]  - 중복 확인용

✔ 선택값 입력 배열      : int[]

 

 

📍 실행 과정

1. 종료 조건
2. 재귀 위한 for문
   - 순열 : for문, 0부터 시작 / 조합 : for문, startIdx부터 시작
   1) 결과값 추가
   2) 재귀               ; 함수 호출할 때마다 매개변수 값 갱신하는 식으로 동작

public static void recur(int startIdx, int depth) {
    // 1) 재귀 종료 조건
    if(depth == M) {
        return;
    }


    // 2) 재귀 위한 for문
    for(int i = 0 ; i < N ; i++) {
        result[depth] = A[i];	// 결과값 배열 갱신
        
        (방문 여부 체크 - 중복X인 경우)
        
        recur(num + 1);	// 🔔 재귀
    }
}

 

 

📍 문제 유형

• 조합 / 순열 생성
• 그래프 문제 - 경로 탐색, 연결 요소 찾기, MST 등
• 최적화 문제 - 최적해 탐색
• 외판원 순회 문제 (TSP)
• 제약 조건 확인
• 스도쿠, N-Queens 등 게임과 퍼즐 문제

 

 

➕ 예제

- N과 M 시리즈

ㅇ 리스트 활용

[코드트리/INTERMEDIATE LOW] n개 중에 m개 뽑기 (JAVA)

 

ㅇ 방문 배열 활용

[백준/JAVA] 15657번: N과 M (8)

 

[백준/JAVA] 1759번: 암호 만들기

 

[백준/JAVA] 6603번: 로또

[백준/JAVA] 9663번: N-Queen

[백준/JAVA] 10971번: 외판원 순회 2

[백준/JAVA] 15686번: 치킨 배달

---

(참고)

백트래킹 알고리즘 (Back Tracking)

백트래킹(Backtracking) (수정 2019-10-09)