백트래킹 이란?
백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문에
어떤 경우에 따라 훨씬 빠를수도 있다.
백트래킹 실행 순서
백트래킹은 DFS(깊이 우선 탐색)을 먼저 실행하면서 더 이상 탐색을 진행할 수 없는 상황이면 다시 되돌아 가서(백트래킹) 탐색을 진행한다.
관련 문제를 풀어보면 이해가 잘 될 것이다.
백트래킹 단계
조금 더 복잡한 백트래킹 문제 1
www.acmicpc.net
N과 M (1) 풀어보기
자연수 N이 주어지면 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하면 된다.
예를 들어,
N : 3 , M : 3 일때, 중복 없이 아래 처럼 출력시키면 된다.
------------------------------------------------
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
일단 for문을 돌면서
for(int i=1; i<=N; i++) {
arr[index] = i; // i를 배열에 넣는다.
visited[i] = true; // i를 방문했다고 체크
recursion(index + 1); // 다음 인덱스 원소를 넣기 위해 (index+1)재귀 호출을 한다.
visited[i] = false; // 위에 recursion이 끝났으므로, 다음 i로 넘어가기 전에 현재 i의 방문여부를 false로 바꿔준다.
}
- 1-1) i = 1 일 때
1을 방문했다고 표시한 뒤, 다음 1을 방문할 때 -> 이미 방문 했으므로 건너 뛰게 된다. (해당 i의 visited 값 확인)
// visited [O,X,X]
for(int i=1; i<=N; i++) {
if(!visited[i]) {
// 방문 여부 확인! (안했을 경우에만 실행)
visited[i] = true; // 방문 안했으면 해당 i의 visited 값을 true로 변경!
}
}
- 1-2) 현재 i는 2이다.
그다음 2를 방문할때는 visited[2] = false 이므로 방문 한다.
또 for문으로 1,2,3을 재 방문을 하기전에, i = 1, 2 -> 이미 방문 했기 때문에 건너 뛰게 되고, 3 은 visited[3] = false 이기 때문에, 방문할 수 있다.
//visited [O,O,X]
for(int i=1; i<=N; i++) {
if(!visited[i]){
// i=3일 경우에만 해당!
visited[3] = true;
arr[index] = 3;
recursion(index + 1);
}
}
재귀 호출을 할때 넘겨주는 index값이 M과 같아 지는 시점에 출력을 하도록 한다.
// visited [O,O,O]
// arr [1,2,3]
// index = 3 , M = 3
if(index == M){ // 넘겨 받은 index가 M과 같아지는 시점에 실행
for(int i=0; i<M; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
- 1-3) 현재 i는 3이다.
여기서 우리가 3을 방문 할 수 있는 이유는? 우리는 전에 1 -> 2-> 3 순으로 방문을 했기 때문에 visited[3]=true로 설정 되어 있을 것이다.
이전에 1->2->3을 종료 한 뒤에, 다시 visited[3]을 false로 바꿔 주어야 하고,
다시 1->2를 종료 할 때도, visited[2]를 false로 바꿔 주어야 한다.
이것을 코드로 나타 내면 ?
for(int i=1; i<=N; i++) {
arr[index] = i;
visited[i] = true;
recursion(index + 1);
// recursion이 끝나면, 자식 노드를 방문을 다했다는 의미이므로 다시 visited[i] = false로 변경
visited[i] = false; // * 이 부분!
}
그럼 다시 이전 단계로 되돌아 가면,
- 1-3) i = 3일 때
visited[3] = true로 체크 해주고, 넘겨 받은 index(2)에 i값인 3을 넣어준다.
// visited [O,X,O]
for(int i=1; i<=N; i++) {
if(!visited[i]){
visited[i] = true;
arr[index] = i;
recursion(index + 1);
visited[i] = false;
}
}그리고 다음 1,2,3 노드들을 방문을 하게 되면,
- 1-3-2) visited[1], visited[3] = true;
유일하게 남은 노드는 2이므로 visited[2] = true, 넘겨 받은 index에 현재 i(2)값을 넣어준다.
// visited [O,O,O]
// arr [1,3,2]
// index = 2, M = 3
for(int i=1; i<=N; i++) {
// 1, 3 건너 뜀. i=2일 때만 실행
if(!visited[2]){
visited[2] = true;
arr[index] = 2;
recursion(index + 1);
visited[2] = false;
}
}여기서 recursion(index + 1) -> recursion(3) 을 호출하게 되면,
if(index == M){ // index : 3, M : 3
for(int i=0; i<M; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} 출력
1 3 2
이대로 계속 반복하면 된다.
전체 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] arr;
static boolean[] isUsed;
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M+1];
isUsed = new boolean[N+1];
recursion(0);
bw.flush();
bw.close();
}
private static void recursion(int K) throws IOException {
if (K == M) { // 모든 배열의 원소가 찼을 때,
for (int i = 0; i < M; i++) {
bw.write(arr[i] + " ");
// 만약 여기서 배열의 들어있는 값의 방문여부를 false로 해주는건? -> 그러면 다시 돌아갔을 때, 중복이 나오게 된다.
// ex) isUsed[arr[i]] = false; ? 어떻게 될까?? X
}
bw.write("\n");
return ;
}
for (int i = 1; i <= N; i++) { // [1, ] [2, ] [3, ] 이런식으로 호출하게끔
if (!isUsed[i]) { // 사용 안했을 때만, 실행
arr[K] = i; // arr[인덱스]에 i값을 넣어주고
isUsed[i] = true; // 방문 여부 표시!
recursion(K + 1); // 배열의 다음 칸을 채우기 위해서 K를 +1해주고 다시 재귀로 돌린다. K++를 해주면 안되는 이유: for문을 돌렸을때, IndexOutOfBoundExcepiton 발생 간으!
isUsed[i] = false; // recursion이 다 수행됐다면, 출력도 끝났다는 의미이니, 이제 해당 i값이 유지될때, 방문여부를 없애준다.(어차피 현재 for문은 이전 i값을 사용 안한다.)
}
}
}
}
