Backtracking

Brute Force

• 단순히 가능한 모든 경우 확인
• 테스트 케이스의 크기에 따라 소요 시간이 엄청나게 커질 수 있음
• 표본의 수와 시간복잡도 고려해 선택해야함

 

매직넘버 100,000,000

• 총 연산수가 약 1억회 이하 -> 충분히 완전탐색으로 접근 가능
• 대략적인 완전탐색 가능 기준으로 잡으면 유용

재귀함수 이용

 

Backtracking

• 완전탐색처럼 모든 경우를 탐색하나 중간 중간에 조건에 맞지 않는 케이스를 가지치기하여 탐색 시간 줄임
• 일반적으로 완전탐색에 비해 시간적으로 효율적
• 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야하기 때문에 재귀 사용하는 경우 많음
• 조건을 어떻게 설정하고 틀렸을 시 어떤 시점으로 돌아가야할지 설계 잘해야함

 

예제 

import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
	public static int[] arr;
	public static boolean[] visit;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[m];
		visit = new boolean[n];
		dfs(n,m,0);
		bw.flush();
		br.close();
		bw.close();
	}

	public static void dfs(int n, int m, int k) {
		// TODO Auto-generated method stub
		if(k==m) {
			for(int a:arr) {
				System.out.print(a+" ");
			}
			System.out.println();
			return;
		}
		for (int i = 0; i < n; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[k] = i+1;
				dfs(n,m,k+1);
				visit[i] = false;
			}
		}
	}

}

 

 

 

c++ next_permutation

int a[3] = {1,2,3};
do{
    for(int i=0;i<3;i++)
    	cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3)};

/*
123
132
213
231
312
321
*/