백트래킹

백트래킹 기법

• 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감.
• 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
• 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

백트래킹을 이용한 알고리즘

1. 상태 공간 트리의 깊이 우선 검색을 실시한다.
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

단순 순열

package day0323_백트래킹;

//반복문
public class 순열_1 {
	static int[] nums;
	static int N;
	
	public static void main(String[] args) {
		nums = new int[] {0,1,2};
		N = nums.length;
		
		for(int i = 0 ; i<N;  i++) {
			for(int j = 0  ; j<N; j++) {
				if(i != j) {
					for(int k = 0 ; k<N; k++) {
						if(i != k && j != k) {
							System.out.printf("%d %d %d\n", nums[i], nums[j], nums[k]);
						}
					}
				}
			}
		}
	}
}
//
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

swap을 통한 순열 생성

package day0323_백트래킹;

import java.util.Arrays;

//swap
public class 순열_2 {
	static int[] nums; //배열
	static int N; //원소수
	
	public static void main(String[] args) {
		nums = new int[] {0,1,2};
		N = nums.length;
		
		perm(0);
		
	}
	
	//idx : 현재 판단 하는 위치
	public static void perm(int idx) {
		//기저조건
		if(idx == N) {
			System.out.println(Arrays.toString(nums));
			return;
		}
		//재귀조건
		for(int i = idx; i < N; i++) {
			swap(i, idx);
			perm(idx+1);
			swap(i, idx); //원상복구 하는 과정이 필요함. why?
		}
		
	}
	
	
	
	
	//swap 메서드 
	//바꿀 인덱스 2개가 인자로 넘어와야한다. (배열을 static 하게 만들었으니까)
	//위의 경우가 아니라면 배열까지 인자로 같이 넘겨줘야한다.
	public static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
}
//
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 1, 0]
[2, 0, 1]

방문체크를 통한 순열 생성

package day0323_백트래킹;

import java.util.Arrays;

//visited
public class 순열_3 {
	static int[] nums;
	static int N;
	static boolean[] visited; //해당 원소 사용 유무
	static int[] result; //순열결과 저장
	
	public static void main(String[] args) {
		nums = new int[] {0,1,2};
		N = nums.length;
		result = new int[N];
		visited = new boolean[N];
		
		perm(0);
	}
	
	public static void perm(int idx) {
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		//모든 요소를 반복문을 통해 돌면서
		//사요하지 않은 원소가 있다면 결과에 넣고 사용했다고 표시도 하고 
		//다음 차례로 내려가 본다.
		for(int i = 0 ; i<N; i++) {
			//1. 원소를 사용했는지 쳌
			if(visited[i]) continue;
			//요기에다가 작성 (실행된다는 것은 안쓴 원소다)
			result[idx] = nums[i];
			visited[i] = true; //해당원소 썼어요~
			perm(idx+1); //내려가
			visited[i] = false; //다시 원상복구

		}
	}		
}
//
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

비트마스킹을 이용한 순열

package day0323_백트래킹;

import java.util.Arrays;

//bitmasking
public class 순열_4 {
	static int[] nums;
	static int N;
	static int[] result; //순열결과 저장
	
	public static void main(String[] args) {
		nums = new int[] {0,1,2};
		N = nums.length;
		result = new int[N];
		
		perm(0, 0);
	}
	
	//idx : 현재 판단하고 있는 위치
	//visited: 사용한 원소를 기록하기 위한 정수
	public static void perm(int idx, int visited) {
//		if(visited == (1<<N)-1)) 이런식의 표현도 가넝 (우마이)
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		//모든 원소를 돌면서 판단해~
		for(int i = 0 ; i<N; i++) {
			//현재 내가 i번째 원소를 사용했다면 쳐내
			if((visited & (1<<i)) != 0 ) continue;
			
			result[idx] = nums[i]; //결과저장
			perm(idx+1, visited | (1<<i));			
		}	
	}
}
//
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]