[알고리즘] 백트래킹(backtracking)이란?, 백준 15649번

백트래킹은 모든 경우의 수를 탐색해서 최적의 해를 구하는 알고리즘입니다.
탐색을 하다가 주어진 조건에 맞지 않으면 이전으로 돌아가 다른 경우의 수를 찾는 방식입니다. 리프노드까지 무조건 탐색하는 DFS 방식과 차이점입니다.

그렇기 때문에 모든 경우의 수를 고려해서 특정 조건을 뽑아야 한다면 백트래킹 방법을 사용하는 것이 좋습니다.

하지만 마찬가지로 모든 경우의 수를 찾기 때문에 특정 조건을 뽑는 과정인 가지치기를 제대로 하지 못한다면 좋은 효율을 낼 수 없습니다.

간단한 백트래킹 예시를 들어보면, 4명의 사람 중 2명을 뽑아 줄 세운다고 생각해봅시다. 수열로 생각하면 4P2로 쉽게 구할 수 있지만 우리는 재귀적으로 구해보겠습니다.

4명 중 1명을 뽑고,
남은 3명 중 1번이랑 나열하고, 2번이랑 나열하고, 3번이랑 나열하고 모두 끝나면 다시 위로 올라가 첫 번째 사람을 바꾸고 다시 두 번째 사람을 바꿔나갑니다. 이렇게 구하는 게 재귀적인 방법입니다.
(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

백준 문제를 보면서 다시 생각해보면,

---

N과 M이 각각 4과 2일 때,
조건에 맞는 숫자를 담을 배열과 방문 여부를 검사할 배열을 만들어줍니다. visited 배열을 통해 방문했으면 true, 아니면 false로 표현해줍니다. 백트래킹에서 다음으로 올 수 있는 숫자를 유망성이 있다라고 하며 위 경우엔 방문하지 않은 숫자들이 유망성 있는 숫자입니다.

첫 번째 숫자를 고르기 위해 반복문으로 1부터 탐색하고 방문한 적이 없으니 배열에 담아주고 재귀함수로 다시 호출을 합니다.

visited 배열: [true, false, false, false]
출력 배열 : [1, 0]

두 번째 숫자를 고르기 위해 1부터 4까지 탐색합니다. 1은 이미 확인한 숫자니 지나가고 2를 담아주고 다시 재귀적으로 호출을 합니다.

visited 배열: [true, true, false, false]
출력 배열 : [1,2]

재귀 함수 맨 위에 탈출조건으로 배열이 가득 찬 경우 출력해주고 함수를 return을 해주도록 합니다.
바로 직전 반복문은 두 번째 숫자를 고르던 반복문입니다. 다시 되돌아가서 2를 false로 만들어줍니다.

visited 배열: [true, false, false, false]
출력 배열 : [1, 2]

이어서 반복문을 수행하면 숫자 3을 확인하고, vistied함수에 체크하고 3을 담아줍니다.

visited 배열: [true, false, true, false]
출력 배열 : [1, 3]

만약 N=4에 M=3이라면
첫 번째 숫자 후보 1 2 3 4
두 번째 숫자 후보 1 2 3 4
세 번째 숫자 후보 1 2 3 4
마지막 줄 조건에 해당하는 3, 4는 출력되고 반복문이 끝나면 두 번째 반복문의 3으로 이동해서 다시 세번째 반복문이 실행됩니다.
첫 번째 숫자 후보 1 2 3 4
두 번째 숫자 후보 1 2 3 4
세 번째 숫자 후보 1 2 3 4

좀 자세하게 풀어썼는데 결국은 이런 흐름으로 호출과 반환을 반복하며 조건에 맞는 수를 고르는 문제입니다.

이후로 풀어 볼 다양한 백트래킹 문제들도 다 비슷한 흐름입니다. 단지 위 문제는 중복되지 않은 숫자를 고르는게 조건이였다면 다른 문제들은 그 조건들이 좀 더 까다롭습니다.

public class Main {
    static int N, M;
    static int[] list;
    static boolean[] visited;

   public static void recurs(int index) {
        if (index == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println();
            return;
        }
		// 숫자 1부터 N까지 반복
        for (int i = 1; i <= N; i++) {  
            // 방문하지 않았으면 출력 배열에 담고 방문했다는 표시를 한다
            if (!visited[i]) {
                list[index] = i;
                visited[i] = true;

              // 다음번 자리에 들어갈 숫자 구하러 재귀
                recurs(index + 1);
                // 재귀 마치고 기존 반복문을 계속 이어감.
                //모든 자리수를 채우고 탈출 조건을 만족해서 return이 되야 아래로 진행
                visited[i] = false;
            }
        }
    }

   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());
        visited = new boolean[N + 1]; //  0번 인덱스 버리고 1번부터 체크하도록
        list = new int[M]; // 출력할 M개
        recurs(0);
    }
}