[백트래킹] 백트래킹의 설명과 간단한 예제풀이

백트래킹(Backtracking)

1. 백트래킹이란?

백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.

 

가장 중요한 점은 제한조건을 위배한다면 그 노드를 제외한다는 점이다.

 

백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다.

여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다.

 

따라서 한마디로 정의하면 DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요가 없는 부분을 쳐내는 행위를 백트래킹(가지치기) 이라고 생각하면된다.

 

그러면 이제 백트래킹에 간단한 예제를 살펴보자

 

2. 백트래킹 - N 과 M (1) 

15649번: N과 M (1)

 

 

import java.util.Scanner;

public class Main {

	public static int[] arr;
	public static boolean[] visit;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		// 4 2   3 1 
		arr = new int[M];
		visit = new boolean[N];
		dfs(N, M, 0);
		
	}

	public static void dfs(int N, int M, int depth) {
		if(depth == M) {
			for(int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = i+1;
				dfs(N, M, depth + 1);
				
				visit[i] = false;
			}
		}

	}
}