---

⚡ 백트래킹

---

📌 백트래킹(Backtracking)

1. 여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택한다.
2. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
3. 이런 선택을 반복하면서 최종 상태에 도달한다.

• 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다.

🔷 백트래킹과 깊이 우선 탐색과의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임.

💡 Prunning(가지치기) 라고 한다.

• 깊이 우선 탐색이 모든 경로를 추적한다면 백트래킹은 유망성 검사를 통해 불필요한 경로를 조기에 차단한다.

❗ 깊이 우선 탐색을 가하기에 경우의 수가 너무 많을 때 가장 바람직하지만 최악이 경우에는 여전히 지수함수 시간을 요하므로 처리가 불가능할 수 있다.

🔷 N-Queen 문제

• NxN 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제

  어떤 두 Queen도 서로를 위협하지 않아야한다. 이 때, Queen을 배치한 n개의 위치는?

• 완전탐색은 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 전부 탐색하기 때문에 굉장히 비효율적인 방식이 된다.

• 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking)다음 자식 노드로 간다.

• 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.

🌟 백트래킹에 정해진 정답은 없다!

---

📌 순열(Permutation)

🔷 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

• 서로 다른 n개 중 r개를 택하는 순열: nPr

💡 nPr은 다음과 같은 식이 성립한다.
nPr = n x (n-1) x (n-2) x ... x (n-r+1)
nPn = n! (Factorial)

• 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다.

• N개의 요소들에 대해서 n! 개의 순열들이 존재한다.

• 사전적 순서도 있지만 최소 변경을 통한 방법도 있다.

  💡 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성된다는 점을 이용한다.

🖥 최소 변경을 통한 순열 출력(swap)

import java.util.Arrays;

public class DailyClass {
	public static int [] nums; // 배열
	public 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);
		}
	}
	
	// nums 배열을 static하게 처리 했기 때문에 매개변수로 받지 않아도 처리 가능
	public static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
}

🖥 최소 변경을 통한 순열 출력(방문 체크)

import java.util.Arrays;

public class DailyClass {
	public static int [] nums; // 배열
	public static int N; // 원소수
	public static int [] result; // 결과저장
	public static boolean[] visited; // 해당 원소 사용 유무
	
	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);
	}
	
	// 최소 변경을 통한 순열 출력
	// idx: 현재 판단 위치
	public static void perm(int idx) {
		// 기저조건
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		// 사용할 수 있는 모든 원소 체크
		for(int i = 0; i < N; i++) {
			if(visited[i]) continue; // 이미 사용한 원소일 때 생략
			
			result[idx] = nums[i]; // 해당 i번째의 원소를 저장
			visited[i] = true;	   // i번째 원소 사용했다고 표시
			perm(idx+1);
			visited[i] = false;	   // i번째 원상복구
		}
	}
}

🌟 비트마스킹을 활용할 수도 있다.

import java.util.Arrays;

public class DailyClass {
	public static int [] nums; // 배열
	public static int N; // 원소수
	public 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(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		// 사용할 수 있는 모든 원소 체크
		for(int i = 0; i < N; i++) {
			// 해당 원소를 썼는지 체크
			if((visited & (1<<i)) > 0) continue;
			result[idx] = nums[i]; // 결과저장
			perm(idx+1, visited | (1 << i));
		}
	}
}

❗ 중복된 값이 포함된 배열의 순열을 체크할 때 같은 순열을 중복 출력할 수 있다. 이 때는 next_permutation을 사용할 수 있다. 이건 나중에 알아보자.