[알고리즘/JAVA] 완전탐색 - 백트래킹

 

완전 탐색이란?

모든 경우의 수를 시도해 보는 방법
반드시 답을 찾을 수 있지만 전부 탐색하기에 시간 복잡도가 일반적으로 높다.

• 완전탐색 기법 종류
  • Brute Force
  • BFS/DFS
  • 백트래킹(Backtracking)
  • 비트마스크(Bitmask)

 

---

 

백트래킹

여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하면서 최종 상태에 도달한다.
- 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다.

백트래킹 기법
▪ 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감.
▪ 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
▪ 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다

백트래킹과 깊이 우선 탐색(DFS)과의 차이
▪ 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임. (Prunning 가지치기)
▪ 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단.
▪ 깊이 우선 탐색을 가하기에는 경우의 수가 너무나 많음.
즉, N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 가하면 당연히 처리 불가능한 문제.
▪ 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수시간(Exponential Time)을 요하므로 처리 불가능

백트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행된다.

1. 상태 공간 트리의 깊이 우선 검색을 실시한다.
2. 각 노드가 유망한지를 검사한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

 

---

백트래킹 종류

문제를 풀때 자주 쓰이는 백트래킹 방식을 4가지로 나누어 보자.

1. N개 중 중복을 허용해서 M개를 순서 있게 나열하기(순열 탐색 - 중복O)
2. N개 중 중복 없이 M개를 순서 있게 나열하기(순열 탐색 - 중복X)
3. N개 중 중복을 허용해서 M개를 고르기(조합 탐색 - 중복O)
4. N개 중 중복 없이 M개를 고르기(조합 탐색 - 중복X)

 

1. N개 중 중복을 허용해서 M개를 순서 있게 나열하기(순열 탐색 - 중복O)

[1, 2, 3, 4, 5] 5개의 숫자를 중복을 허용해서 3개를 순서 있게 나열하는 경우의 수를 생각해보자.
3자리의 공간에 5개의 숫자가 모두 올 수 있으므로 5³ = 125가지 경우의 수가 있을 것이다.
시간 복잡도 : O(N^M)
공간 복잡도 : O(M)

예시 문제 : 백준 15651 - N과 M(3)
https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] series;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		series = new int[M+1];
		// NM 함수는  1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법 출력
		NM(1);
		System.out.println(sb.toString());
	}
	static private int NM(int d) {
		// 깊이가 끝에 도달 > 출력
		if(d == M+1) {
			for (int i = 1; i <= M; i++) {
				sb.append(series[i]).append(' ');
			}
			sb.append('\n');
		}
		// 하나씩 경우의 수를 대입하며 다음깊이로 이동
		else {
			for (int i = 1; i <= N; i++) {
				series[d] = i;
				NM(d+1);
			}
		}
		return 0;
	}
}

 

2.  N개 중 중복 없이 M개를 순서 있게 나열하기(순열 탐색 - 중복X)

[1, 2, 3, 4, 5] 5개의 숫자를 중복 없이 3개를 순서 있게 나열하는 경우의 수를 생각해보자.
3자리의 공간에 처음엔 5개, 다음은 4개, 그 다음 3개의 숫자가 올 수 있으므로 5 x 4 x 3 = 60가지 경우의 수가 있을 것이다.
시간 복잡도 : O(_NP_M)
공간 복잡도 : O(M)

예시 문제 : 백준 15649 - N과 M(1)
https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] series;
	static boolean[] check;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		series = new int[M+1];
		check = new boolean[N+1];
		NM(1);
		System.out.println(sb.toString());
	}
	private static void NM(int d) {
		// 깊이의 끝에 도달 
		if(d == M+1) {
			for (int i = 1; i <= M; i++) {
				sb.append(series[i]).append(' ');
			}
			sb.append('\n');
		}
		// 경우의 수 체크해주고 > 다음 깊이로
        	// check 배열을 통해 중복 제거
		else {
			for (int i = 1; i <= N; i++) {
				if(check[i]) continue;
				series[d] = i; check[i] = true;
				NM(d+1);
				check[i] = false;
			}
		}
		return ;
	}
}

 

3. N개 중 중복을 허용해서 M개를 고르기(조합 탐색 - 중복O)

[1, 2, 3, 4, 5] 5개의 숫자를 중복을 허용해서 3개를 고르는 경우의 수를 생각해보자.
5개 중 중복을 허용해 3개를 뽑는 경우의 수는 35이다.

1 1 1 / 1 1 2 / 1 1 3 / 1 1 4 / 1 1 5 / 1 2 2 / 1 2 3 / 1 2 4 / 1 2 5 / 1 3 3 / 1 3 4 / 1 3 5 / 1 4 4 / 1 4 5 / 1 5 5
2 2 2 / 2 2 3 / 2 2 4 / 2 2 5 / 2 3 3 / 2 3 4 / 2 3 5 / 2 4 4 / 2 4 5 / 2 5 5 
3 3 3 / 3 3 4 / 3 3 5 / 3 4 4 / 3 4 5 / 3 5 5 
4 4 4 / 4 4 5 / 4 5 5 
5 5 5

시간 복잡도 : O(N^M)보단 작다(더 정확하게 나타내려면 많은 수식이 필요).
공간 복잡도 : O(M)

 

예시 문제: 백준 15652 - N과 M(4)
https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

import java.util.Scanner;

public class boj15652 {
	static int N, M;
	static int[] series;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		series = new int[M + 1];
		series[0] = 1;
		// NM 함수는  1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법 출력
		NM(1);
		System.out.println(sb.toString());
	}

	private static void NM(int d) {
		// 깊이의 끝에 도달
		if (d == M + 1) {
			for (int i = 1; i <= M; i++) {
				sb.append(series[i]).append(' ');
			}
			sb.append('\n');
		}
		// 경우의 수 체크해주고 > 다음 깊이로
		// start를 통해 순서 제거
		else {
			int start = series[d-1];
			for (int i = start; i <= N; i++) {
				series[d] = i;
				NM(d + 1);
				series[d] = 0;
			}
		}
		return;
	}
}

 

4. N개 중 중복 없이 M개를 고르기(조합 탐색 - 중복X)

[1, 2, 3, 4, 5] 5개의 숫자를 중복 없이 3개를 고르는 경우의 수를 생각해보자.

5개중 3개를 고르는 경우의 수는 ₅C₃ = ₅C₂ = 5 * 4 / 2 = 10이다.
시간 복잡도 : O(_NC_M)
공간 복잡도 : O(M)

예시 문제: 백준 15650 - N과 M(2)
https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

import java.util.Scanner;

public class boj15650 {
	static int N, M;
	static int[] series;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		series = new int[M + 1];
		// NM 함수는  1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법 출력
		NM(1);
		System.out.println(sb.toString());
	}

	private static void NM(int d) {
		// 깊이의 끝에 도달
		if (d == M + 1) {
			for (int i = 1; i <= M; i++) {
				sb.append(series[i]).append(' ');
			}
			sb.append('\n');
		}
		// 경우의 수 체크해주고 > 다음 깊이로
		// start를 통해 순서, 중복 제거
		else {
			int start = series[d-1];
			for (int i = start+1; i <= N; i++) {
				series[d] = i;
				NM(d + 1);
				series[d] = 0;
			}
		}
		return;
	}
}

 

정리

중복	순서	시간 복잡도	공간 복잡도
YES	YES	O(NM)	O(M)
NO	YES	O(NPM)	O(M)
YES	NO	O(NM)보단 작다	O(M)
NO	NO	O(NCM)	O(M)