개념
•
모든 경우의 수를 확인해야 할 때 (순열: 순서 상관 있게 M개에서 N개의 숫자를 선택)
◦
for로는 확인 불가능한 경우(깊이가 달라질때)
▪
예를 들어 1~3(M) 사이에서 2(N)개의 숫자를 고르는 경우의 수는
for문을 2(N)번 돌려서 구할 수 있다. 하지만 M과 N의 수가 정해지지 않을 경우가 있는데 이 경우에 백트래킹을 사용한다.
시간 복잡도
•
N^N: 중복이 가능, 최대 N=8까지 가능
•
N!: 중복이 불가능, 최대 N=10까지 가능
(문제 조건 잘보자)
문제
[백준 15649]
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를 사용하지 않았다고 바꾼다.
}
}
}
Java
복사
