백트래킹

백트래킹

가능한 모든 경우를 탐색하는 중 해답으로 이어지지 않는 경우에 대해서 탐색하지 않고 되돌아가며 해결

• 유망 : 현재 상태가 문제의 해답으로 발전한 가능성이 높은지를 판단하는 기준
• 가지치기 : 탐색 중 불필요한 경로를 제거하여 탐색의 효율성을 높이는 방법
• 유망성이 없는 가정은, 가지치기로 경우의 수를 줄인다.

• 완전 탐색과 다르게 모든 경우의 수를 고려하지 않는다.
• 다만, 최악의 경우에는 지수 함수를 요구하므로 해결이 불가능하다.
  1. 가지치기가 거의 이루어지지 않은 상황
  2. 문제가 매우 큰 입력을 가지는 상황
  3. 유효한 해답이 거의 없는 상황

<예시> N-Queen문제

• 체스 판 위에 N개의 Queen들이 서로 위협하지 않게 배치하는 문제

• 만약 8Queen이라고 하면 모든 경우의 수는 ₆₄C₈ = 4,426,165,368 개이다.
• 실제 정답 수는 92개가 된다.
• 모든 경우의 수 속에서 92개를 최대한 효율적으로 찾아내는 것이 관건

1. 같은 행에는 퀸을 놓을 수 없다.
2. 따라서 모든 경우의 수는 4 4 4 * 4 = 256가지가 된다.
3. 재귀함수를 이용한 구현 방법

<예시2> 민기의 햄버거 다이어트

import java.util.Scanner;

public class test {
	
	static int N, L; // N : 재료의 개수, L : 제한 칼로리 
	static int[] cals;
	static int[] scores;
	static int ans;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			L = sc.nextInt();
			scores = new int[N];
			cals = new int[L];
			
			for(int i = 0; i < N; i++) {
				scores[i] = sc.nextInt();
				cals[i] = sc.nextInt();
			}
			
			ans = 0;
			
			makeBurger(0, 0, 0);
			
			System.out.println("#" + test_case + " " + ans);
		}
	}
	
	
	static void makeBurger(int idx, int sumScore, int sumCals) {
		
		if (sumCals > L) { // 이미 칼로리가 제한을 넘어가게 되는 경우도 고려 
			return;
		}
		
		// 기저 조건 
		if (idx == N) { // 모든 재료를 고려 완료하였을 때
			if ( ans < sumScore) {
				ans = sumScore;
			}
			return; 
			
		}
		
		// 재귀 부분 
		// 재료를 사용한 경우 
		makeBurger(idx + 1, sumScore + scores[idx], sumCals + cals[idx]);
		
		// 재료를 사용하지 않은 경우 
		makeBurger(idx + 1, sumScore, sumCals);
	}
}

---

---

순열

• 서로 다른 원소들을 특정한 순서로 나열하는 것
• 서로 다른 n 개의 원소를 가지는 집합에서 나열하는 경우를 factorial 이라고 한다.
  N! = N * (N-1) * (N-2) * ... * 2 * 1
• N이 12를 벗어나는 경우, 시간 복잡도가 폭팔적으로 증가한다.

---

<중복이 없다는 가정 하에>

순열 구현1 (반복문)

public static void main(String[] args) {
	nums = new int[] {1, 2, 3};
	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 ( k != i && k != j) {
						System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
					}
				}
			}
		}
	}
}

• 반복문이 N개가 필요하고, 중복이 없는 조건이 필요하다면 if 문은 N-1개가 필요하다.

순열 구현2 (swap)

import java.util.Arrays;

public class 순열01_반복문2 {
	
	static int[] nums;
	static int N;
	
	public static void main(String[] args) {
		nums = new int[] {0, 1, 2};
		N = nums.length;
        perm(0);

	}
	
	// 바꿀 배열이 static으로 선언이 되어있는 경우, 인자로 보내지 않아도 된다. 
	static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;
	}
	
	// idx = 현재 판단 위치
	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); // 다음 swap을 위해서 원래대로 돌려줘야 한다. 
		}
	}
}

순열 구현3 (방문체크)

• boolean 을 통하여 진행하는 것으로, 추가적인 공간이 필요하다

import java.util.Arrays;

public class 순열01_방문체크 {
	
	static int[] nums, result;
	static int N;
	static boolean[] visited;
	
	public static void main(String[] args) {
		nums = new int[] {0, 1, 2};
		N = nums.length;
		visited = new boolean[N];
		result = new int[N];
		perm(0);
	}
	
	
	// idx = 현재 판단 위치
	static void perm (int idx) {
		// 기저 조건 
		if(idx == N) {
			System.out.println(Arrays.toString(result));
		}
		
		// 재귀 부분 
		for(int i = 0; i < N; i++) {
			// 사용하지 않은 원소를 갖고 생성 
			if (visited[i]) continue; // 이미 사용하였다면 넘어간다. 
			
			result[idx] = nums[i];
			visited[i] = true;
			perm(idx+1);
			visited[i] = false; // result는 덮어버리기 때문에 덮어쓰지 않아도 된다. 
		}
	}
}

순열 구현4 (비트마스킹)

• boolean과 같이 다른 저장 공간을 사용하는 것이 아니라 비트로 사용 여부를 확인하게 된다.

public class 순열01_비트마스킹 {
	
	static int[] nums, result;
	static int N;
	
	public static void main(String[] args) {
		nums = new int[] {0, 1, 2};
		N = nums.length;
		result = new int[N];

	}
	
	
	// idx = 현재 판단 위치
	// visited = 사용한 원소를 기록하기 위한 정수 
	static void perm (int idx, int visited) {
		// 기저 조건 
		if(idx == N) {
			System.out.println(Arrays.toString(result));
		}
		
		// 재귀 부분 
		for(int i = 0; i < N; i++) {
			// 사용하지 않은 원소를 갖고 생성 
			if ((visited & (1 << i)) != 0) continue; // 이미 사용하였다면 넘어간다. 
			
			result[idx] = nums[i];
			perm(idx+1, visited | (1<<i));
			// 인자로 받아서 넘기게 되는 경우, perm 안에서 연산도 가능하다. 다음 자리를 판단 
		}
	}
}

---

---

순열의 확장 개념

• 중복 순열 : 원소를 뽑을 때 중복을 허용하는 경우 {AA, AB, BA, BB}
• 원형 순열 : 배열할 때 원형으로 배열하는 경우