백트래킹(Backtracking) 알고리즘 - JAVA

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다.

-출처 위키백과

 

 

백트래킹(Backtracking) 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 입니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

 

즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 입니다.  주로 문제 풀이에서는 재귀로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 정의하고 그 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하도록 구현을 하면 됩니다.

 

---

 

백준 N과 M(1) 문제를 예를 들어 설명을 드리겠습니다.

 

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

이 문제는 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제입니다.

 

N가지가 있으면 N가지를 다 할 수 있는데 M개를 어떤 순서로 할건지 고른다고 생각하면 됩니다.

 

첫번째 올 수 있는 수 N가지

두번째 올 수 있는 수 N-1가지

.

.

.

마지막에 올 수 있는수 1개

==> N! 가지로 즉 시간복잡도는 O(N!) 입니다.

 

선택할수 있는 수의 개수	N	N-1	N-2	...	1
위치(INDEX)	1	2	3	...	M

 

 

- 함수의 기능  : 어떤 위치에 올 수 있는 수를 결정할지 모든 경우의 수를 탐색  (DFS)

               ==> 올 수 있는 수는 1 ~ N 수 중에서 앞에서 사용하지 않은 수 (가지치기)

 

- 모든 위치(INDEX)에서 이 함수를 적용하기 때문에 재귀

 

- 위치가 M 일 경우 선택한 수열을 출력한다. 

 

 

 

---

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;
	static boolean c[]; static int a[];
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		c = new boolean[n+1];
		a = new int[n+1];
		
		go(0);
		
		System.out.println(sb);
	}
	
	public static void go(int index) {
		//인덱스가 마지막 위치에 도달하면 수열 출력
		if(index == m) { 
			for(int i=0; i<m; i++) {
				sb.append(a[i]).append(" ");
			}
			sb.append('\n');
			return;
		}
		// 1부터 ~ N개의 수를 선택
		for(int i=1; i<=n; i++) {
			if(c[i]) continue; //이미 선택한적이 있으면 다음으로
			c[i] = true;  // 수 i를 사용
			a[index] = i; //해당 위치에 i를 넣는다.
			go(index+1); //위치를 1증가 시키고 재귀
			c[i] = false; // index 뒤에 일어날 모든 경우를 했기때문에 수 i를 사용하지 않았다고 바꾼다.
		}
	}
}

 

 

 

 

 

봐주셔서 진심으로 감사합니다. 오늘도 행복한 하루 되시길 바랍니다.

댓글로 피드백 주시면 감사하겠습니다

 

 

-참고 https://chanhuiseok.github.io/posts/algo-23/