[알고리즘 기법] 백트래킹 ( 되추적 방법 ) ( Backtracking )

 

◇  설명

-  결정을 내리다가 틀렸다는 것이 분명해지면 최근에 한 결정을 번복하고 다른 결정을 해나가는 알고리즘 설계 기법
-  상태 공간 트리( 찾는 해를 포함하는 트리 )를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘
-  이런 저런 방법이 다 안 될 때, 최후의 수단으로 이용하는 방법.
-  완전 탐색( Exhaustive Search )을 개선함 ( 완전 탐색 = 브루트 포스 ( Brute-force ) )

 

◇  코드

  ex)  순열, 조합

public class Recursion_perm_com {

	static char data[] = { 'a', 'b', 'c', 'd' };
	static final int n = data.length, m;
	static int arr;
	static boolean visited;
	
	public static void func_perm( int k ) {  // 순열
		if( k == m ) {
			for( int i = 0; i < m; i++ )
				System.out.print( data[arr[i]] + " ");
			System.out.println();
			return;
		}
		for( int i = 0; i < n; i++ ) {	
			if( !visited[i] ) {
				visited[i] = true;
				arr[k] = i;
				func( k + 1 );
				visited[i] = false;
			}
		}
	}

	public static void func_com( int k, int s ) {  // 조합
		if( k == m ) {
			for( int i = 0; i < m; i++ )
				System.out.print( data[arr[i]] + " ");
			System.out.println();
			return;
		}
		for( int i = s; i < n; i++ ) {
			if( !visited[i] ) {
				visited[i] = true;
				arr[k] = i;
				func( k + 1, i + 1 );
				visited[i] = false;
			}
		}
	}
	
	public static void main(String[] args) {
    
		m = n;
		arr = new int[n];
		visited = new boolean[n];
        
		// n개 중 m개를 뽑는 순열/조합
        
		arr = new int[n];
		visited = new boolean[n];
		func_perm( 0 );

		arr = new int[n];
		visited = new boolean[n];
		func_com( 0, 0 );
        
	}
}

 

  ex)  멱집합  ( 집합의 모든 부분집합 출력 )

public class Recursion_powerset {

	private static char data[] = { 'a', 'b', 'c', 'd' };
	private static int n = data.length;
	private static boolean include[] = new boolean[n];
	
	public static void powerSet( int k ) {
		if( k == n ) {
			for( int i = 0; i < n; i++ )
				if( include[i] ) 
					System.out.print( data[i] + " " );
			System.out.println();
			return;
		}
		include[k] = false;
		powerSet( k+1 );
		include[k] = true;
		powerSet( k+1 );
	}
	public static void main(String[] args) {
		
		powerSet(0);
	}
}

public class Recursion_com {

	static char data[] = { 'a', 'b', 'c', 'd' };
	static final int n = data.length;
	static int arr[] = new int[n];
	static boolean visited[] = new boolean[n];
	
	public static void func( int k, int s, int m ) {

		if( k == m ) {
			for( int i = 0; i < m; i++ )
				System.out.print( data[arr[i]] + " ");
			System.out.println();
			return;
		}
		for( int i = s; i < n; i++ ) {
			if( !visited[i] ) {
				visited[i] = true;
				arr[k] = i;
				func( k + 1, i + 1, m );
				visited[i] = false;
			}
		}
	}
	
	public static void main(String[] args) {

		for( int i = 0; i <= data.length; i++ )
			func( 0, 0, i );
	}

}

 

  ex)  N-Queens

import java.io.*;

public class Main {

	static int n, cnt, cols[]; // col : 각 row에 놓여지는 col의 idx

	public static void queens(int row) {
		if (!promising(row))
			return;
		else if (row == n) {
			cnt++;
			return;
		}
		for (int col = 1; col <= n; col++) {
			cols[row + 1] = col;
			queens(row + 1);
		}
	}

	public static boolean promising(int row) {
		for (int col = 1; col < row; col++)
			if ((cols[col] == cols[row]) || (row - col == Math.abs(cols[row] - cols[col])))
				return false;
		return true;
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		br.close();

		cols = new int[n + 1];
		
		queens(0);

		System.out.println(cnt);
	}
}

  ( https://hyunjiishailey.tistory.com/175 )

 

◇  출처

  -  설명  --  영리한 프로그래밍 ( 권오흠 ), 알고리즘 개발 방법론 ( 이재규 )
  -  코드  --  영리한 프로그래밍 ( 권오흠 ), 등등