알고리즘 - 백트래킹(Back-Tracking)

백트래킹 이란?

백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문에

어떤 경우에 따라 훨씬 빠를수도 있다.

 

 

백트래킹 실행 순서

백트래킹은 DFS(깊이 우선 탐색)을 먼저 실행하면서 더 이상 탐색을 진행할 수 없는 상황이면 다시 되돌아 가서(백트래킹) 탐색을 진행한다.

 

관련 문제를 풀어보면 이해가 잘 될 것이다. 

 

www.acmicpc.net/step/34

백트래킹 단계

 

 

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값을 사용 안한다.)
            }
        }
    }
}