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

백트래킹 알고리즘은 모든 경우의 수를 탐색하지만, 답이 될 수 없는 경우는 더 깊게 들어가지 않고 되돌아오는(BackTrack) 탐색 기법이다.

기본적인 형태는 DFS(깊이 우선 탐색)을 통해 완전 탐색을 하지만 중간중간 조건에 맞지 않는 경우는 가지치기를 하면서 탐색하는 기법이다.

백트래킹을 사용하는 이유

보통 알고리즘 코딩 테스트에서는 시간초를 1초를 준다.
이 경우 O(100,000,000) 시간 복잡도를 넘는 경우 시간초과가 발생하게 되는데 단순한 완전 탐색은 주어지는 값이 조금만 커지더라도 경우의 수가 급격하게 증가하게 된다.

따라서 불가능한 경우의 수를 중간에 차단(가지치기)을 하지 않으면 시간 초과가 발생하는 일이 많기에 가능한 경우만 끝까지 탐색을 하고 불가능해지는 순간 즉시 되돌아가는 백트래킹 기법을 사용하는 것이다.

백트래킹의 흐름

1. 선택(Choose)
   현재 단계에서 가능한 선택지 중 하나를 선택

• 아직 선택되지 않은 값
• 조건을 만족하는 값
• 규칙을 위반하지 않는 값

이 단계에서는 이 선택이 가능한가? 만 판단

2. 진행(Explore)
   선택한 값을 현재 상태에 반영한 뒤, 다음 단계로 재귀 호출

• 깊이 + 1
• 남은 문제 크기 감소
• 부분 해(partial solution)를 확장

3. 가지치기
   재귀를 더 진행하기 전에 체크

이 상태가 답이 될 가능성이 있는가?

• 이미 조건 위반
• 더 진행해도 불가능한 상태
  => 가능성이 없으면 즉시 중단

4. 되돌리기(Backtrack)
   재귀가 끝나면 상태를 이전으로 복구

• 선택 취소
• 방문 표시 해제
• 값 제거

이 단계가 없으면 다음 경우의 수가 오염이 되기에 가장 중요하다!!!!!!!!!!!!!
백트래킹은 하나의 상태 공간을 공유하기에 모든 재귀 호출에서 함께 사용한다.
그렇기에 무조건!!! 되돌리기를 통해 원 상태로 복구를 시켜놓아야 한다.

백트래킹 알고리즘의 적용 예시

https://www.acmicpc.net/problem/15649

이 문제는 백트래킹 문제의 가장 대표적인 예시의 문제이다.

만약 이 문제에서 전수 조사를 하게 되면
N = 4, M = 2인 경우 P(4,2) = 4 × 3 = 12로 경우의 수가 적지만
N = 8, M = 8인 경우 P(8,8) = 8! = 40,320으로 순식간에 수가 커지게 된다.

그렇기에 문제의 조건에 맞지 않는 경우의 수를 가지치기 하는 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_15649_S3 {
	static int N;
	static int M;
	static boolean[] visited;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 1 ≤ M ≤ N ≤ 8
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N + 1];
		arr = new int[M + 1];

		backtracking(1);
		
		System.out.println(sb);
	}
	
	static void backtracking(int depth) {
		if (depth == M + 1) {
			for (int i = 1; i < M + 1; i++) {
				sb.append(arr[i]).append(" ");
			}
			sb.append("\n");
			
			return ;
		}
		
		for (int i = 1; i < N + 1; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[depth] = i;
				backtracking(depth + 1);
				visited[i] = false;
			}
		}		
	}
}

이 문제에서 가장 중요한 부분은

		for (int i = 1; i < N + 1; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[depth] = i;
				backtracking(depth + 1);
				visited[i] = false;
			}
		}

이며 visited[i] = true로 방문을 한 후 재귀가 끝나면 다시 false로 바꿔 상태를 이전으로 북구를 하는 것이 백트래킹 문제의 핵심이다.