• 지금 경로가 해결책으로 이어질 것 같지 않으면 더 이상 가지 않고 되돌아가(Backtrack) 다시 해를 찾는 기법
• 가능한 모든 경우의 수를 확인하되, 정답이 될 가능성이 없는 길은 미리 포기해서 효율을 높임
• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

문제 유형

1) N-Queen 문제

• $N \times N$ 체스판 위에 $N$개의 퀸을 서로 공격하지 못하게 배치하는 문제
• 첫 번째 줄에 퀸을 놓고, 두 번째 줄에 퀸을 놓을 때 위쪽 퀸과 공격 경로가 겹치는지 확인
• 겹친다면(유망하지 않다면), 그 자리는 포기하고 바로 옆 칸으로 이동 (굳이 그 밑으로 계속 내려가서 확인하지 않음)

2) 부분 집합의 합 (Subset Sum)

• 집합에서 원소를 골라 합이 특정 숫자가 되는 경우를 찾음
• 숫자를 하나씩 더해보다가, 이미 목표 숫자를 넘어버렸다면 더 이상 숫자를 더해보지 않고 뒤로 돌아가 다른 조합을 찾음

코드 예시

import java.io.*;
import java.util.*;
public class Main {

	static Scanner sc= new Scanner (System.in); 
	static int N,M;
	
	static int path[];
	//idx : 주사위 눈금(1~6), val : 사용여부
	static int used[] = new int[7];
	static void func1(int lev) {
		if(lev == N) {
			for(int i=0; i<N; i++) {
				System.out.print(path[i]+" ");
			}
			System.out.println();
			return;
			
		}
		for(int i=1; i<=6; i++) {
			path[lev] = i;
			func1(lev+1);
			path[lev] = 0;
		}
	}
	static void func2(int lev) {
		//backtracking은 일단 들어간다음에 별로면 바로나옴 : return
		//if(lev>=2 && path[lev-2] > path[lev-1])return;
		//기저조건
		if(lev == N) {
			for(int i=0; i<N; i++) {
				System.out.print(path[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i=1; i<=6; i++) {
			//가지치기는 들어가지를 않음 : continue
			if(lev >=1 && path[lev-1] > i)continue;
			path[lev] = i;
			func2(lev+1);
			path[lev] = 0;
		}
	}
	
	
	static void func3(int lev) {
		if(lev == N) {
			//path에 저장해둔거 출력하고
			for(int i=0; i<N; i++) {
				System.out.print(path[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=1; i<=6; i++) {
			if(used[i] == 1)continue;
			path[lev] = i;
			used[i] = 1;
			func3(lev+1);
			path[lev] = 0;
			used[i] = 0;
		}
	}
	
	public static void main(String[] args) {
		N = sc.nextInt();
		M = sc.nextInt();
		path = new int[N];
		
		if(M==1) func1(0);
		if(M==2) func2(0);
		if(M==3) func3(0);
	}
}