백트래킹 기법(Backtracking)

1. 백트래킹(Backtracking)

: 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아가는 기법

(1) 최적화(Optimization) 문제

(2) 결정(Decision) 문제 : 문제 조건을 만족하는 해의 존재 여부를 'Yes' or 'No'가 답하는 문제

(ex> 미로 찾기, n-Queen 문제, Map coloring, 부분 집합의 합 등)

 

(3) 알고리즘 절차

① 상태 공간 TREE의 DFS(깊이 우선 검색)

② 각 노드의 유망성 점검 - 해답을 포함했는가?

③ 노드가 유망하지 않다면, 부모 노드로 돌아가서 검색(pop)

 

 

 

 

2. 미로 찾기(결정 문제)

(1) 문제

- 입구, 출구 주어진 미로에서 입구~출구까지 경로 찾기

- 이동 방향은 위, 아래, 오른쪽, 왼쪽 4방향

 

 

(2) 풀이

- 이동 상황을 Stack에 push (더 이상 갈 수 없을 때까지)

- 더 이상 진행할 수 없다면, 진행할 수 있는 상태로 되돌아감(Stack pop)

(단, 탐색 순서는 시계 방향 or 반시계 방향 임의로 선택)

 

(3) 코드

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;

class Maze
{
	public static void main(String args[]) throws Exception
	{
		System.setIn(new FileInputStream("Stack2/res/maze.txt"));
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		sc.nextLine();
		int[][] mazeArray = new int[8][8];
		boolean[][] invalid = new boolean[8][8];
		for(int i = 0; i < size; i++) {
			String[] s = sc.nextLine().split("");
			for(int j = 0; j < size; j++) {
				mazeArray[i][j] = Integer.parseInt(s[j]);
			}
		}
		Stack<int[]> stack = new Stack<int[]>();
		//HashMap<int[], Action> hash = new HashMap<>();
		boolean[][] visited = new boolean[size][size];
		backtrack(mazeArray, stack, size, visited);
	}
	
	public static void backtrack(int[][] mazeArray, Stack<int[]> stack, int size, boolean[][] visited) {
		int[][] d = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		stack.push(new int[]{0, 0});
		visited[0][0] = true;
		int[][] answer;
		while(!stack.isEmpty()) {
			int[] target = stack.peek();
			boolean flag = false;
			if(target[0] == size-1 && target[1] == size-1) {
				answer = new int[stack.size()][2];
				int index = answer.length-1;
				while(!stack.isEmpty()) {
					answer[index--] = stack.pop();
				}
				for(int i = 0; i < answer.length; i++) {
					System.out.println(answer[i][0] + " " + answer[i][1]);
				}
				break;
			}
			else {
				for(int i = 0; i < 4; i++) {
					int newx = target[0] + d[i][0];
					int newy = target[1] + d[i][1];
					if(newx >= 0 && newx < size && newy >= 0 && newy < size) {
						if(mazeArray[newx][newy] == 0 && !visited[newx][newy]) { //visited 끝난 곳은 다시 가지 않음으로 백트래킹 처리
							stack.push(new int[] {newx, newy});
							visited[newx][newy] = true;
							flag = true;
							break;
						}
					}
				}
				if(!flag) {
					int[] s = stack.pop(); //현재 위치에서 갈 수 있는 곳이 없음 -> 되돌아가기
				}
			}
		}
	}

 

 

 

 

 

 

 

 

3. DFS와의 비교

백트래킹	깊이 우선 탐색(DFS)
불필요한 경로의 조기차단 (가지치기 = Pruning)	모든 후보, 경로를 추적
일반적으로 N!보다 경우의 수 감소 BUT 최악의 경우에는 여전히 지수함수 시간 요구	N!가지 경우의 수를 다 파악해야

- 유망성 : 노드 방문 시, 그 노드를 포함한 경로가 해답이 될 수 있는 정도

 

 

 

 

 

 

 

4. N-Queen 문제

(1) 문제

- n*n 정사각형 공간, n개의 queen

- 조건 : 모든 queen이 자신의 일직선상 및 대각선상에 아무것도 놓이지 않아야 함

ex> 4x4 공간인 경우의 상태공간 tree

 

 

(2) 결과(상태 TREE 노드 개수)

- 깊이 우선 탐색 : 1+ (1+4+16+64) + (1+4+12+48) + 4 = 85 + 65 + 4 = 155

- 백트래킹 : 1+ (1+4+8+4) + (1+4+4) = 17 + 9 = 27

▶ 수행시간을 1/5로 감소 가능

 

 

 

 

***후보군 설정 문제***

5. Power Set문제

(1) Power Set에 관하여

- 어떤 집합의 공집합 + 자기자신을 포함한 모든 부분집합

- (원소의 개수가 n일때) 부분집합의 개수 = 2^n개

 

 

(2) 백트래킹 기법으로 구하기

- 배열 arr : 원소들을 담은 집합

- 배열 a : 각 원소의 부분집합 포함 여부를 나타낸 배열 활용(boolean)

- k, limit : limit 범위 내에서 k번째 원소를 탐색 중

- make_candidates : a[k]에 넣을 값의 후보군을 생성하는 함수

- backtrack : k가 limt에 도달할 때까지 재귀를 통해 백트래킹하는 함수

- process_solution : 부분집합을 출력하는 함수

(참고 : kim6394.tistory.com/159)

import java.util.Scanner;

public class Powerset {
	static int[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		arr = new int[size];
		for(int i = 0; i < size; i++) {
			arr[i] = sc.nextInt();
		}
		boolean[] a = new boolean[arr.length]; //원소 사용여부
		backtrack(a, 0, a.length);
		
	}
	
	public static int make_candidates(boolean[] a, int k, int limit, boolean[] c) {
		//후보군 저장 배열 c
		c[0] = true;
		c[1] = false;
		return 2;
	}
	
	public static void backtrack(boolean[] a, int k, int limit) {
		boolean[] c = new boolean[a.length];
		if(k == limit) {
			process_solution(a, k); // 출력
		}else {
			int ncands = make_candidates(a, k, limit, c); //후보군, c를 매개변수로 넣으면 반영된다...!
			for(int i = 0; i < ncands; i++) {
				a[k] = c[i];
				backtrack(a, k+1, limit); //재귀로 백트래킹
			}
		}
	}
	
	public static void process_solution(boolean[] a, int k) {
		for(int i = 0; i < a.length; i++) {
			if(a[i])	System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

 

 

 

 

6. 순열

- 후보군 : 아직 쓰지 않은 모든 원소가 대상

- 5번과 유사하지만 후보군의 범위 변경 → 앞에서부터 위치할 원소의 "index"를 담은 배열을 사용

import java.util.Scanner;

public class Permutation {
	static int[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		arr = new int[size];
		for(int i = 0; i < size; i++) {
			arr[i] = sc.nextInt();
		}
		int [] a = new int[arr.length]; //원소들 담는 배열
		backtrack(a, 0, a.length);
		
	}
	
	public static int make_candidates(int[] a, int k, int limit, int[] c) {
		boolean[] in_perm = new boolean[a.length];
		for(int i = 0; i < k; i++) {
			in_perm[a[i]] = true; //이미 쓰인 원소는 true 처리
		}
		int ncands = 0;
		
		for(int i = 0; i < limit; i++) {
			if(!in_perm[i]) { //아직 쓰이지 않은 원소 index를 후보군으로 담아줌 (다음 경로)
				c[ncands] = i;
				ncands++;
			}
		}
		return ncands;
	}
	
	public static void backtrack(int[] a, int k, int limit) {
		int[] c = new int[a.length];
		if(k == limit) {
			process_solution(a, k); // 출력
		}else {
			int ncands = make_candidates(a, k, limit, c); //후보군, c를 매개변수로 넣으면 반영된다...!
			for(int i = 0; i < ncands; i++) {
				a[k] = c[i];
				backtrack(a, k+1, limit); //그 다음 원소
			}
		}
	}
	
	public static void process_solution(int[] a, int k) {
		for(int i = 0; i < a.length; i++) {
			System.out.print(arr[a[i]] + " ");
		}
		System.out.println();
	}
}

(그림 출처 : swexpertacademy.com/main/learn/course/lectureVideoPlayer.do)