[Coding Test] Algorithm(1)

1. 백트래킹

• 완전탐색처럼 모든 경우를 탐색하지만, 탐색 중간에 조건에 맞지 않는다면 가지치기를 통해 탐색 횟수를 줄이는 방법
• 탐색 종료 조건과 언제 가지치기 할 지가 가장 중요하다
• 대표적인 완전탐색 방식으로 DFS가 있다.

과정

백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적이다. 하지만, N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸려서 처리가 불가능할 수도 있다. 따라서, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다! 즉, 답이 될만한 가능성이 없으면 더 이상 탐색을 진행하지 않고 가지치기를 하면서 최적해를 구하는 것이다.

주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어서 답이 절대로 될 수 없는 상황을 정의하고, 그런 상황일 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현할 수 있다.

백트래킹의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드 (부모)로 돌아가 (Backtracking) 다음 자식 노드로 이동한다.

해가 될 만한 가능성이 있으면 유망하다 (promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기 (pruning)라고 한다.

2. 실전문제

N과 M(1) (백준 15649) - 백트래킹

import java.io.*;
import java.util.StringTokenizer;

public class P15649_N과M1 {
    static int[] arr;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   // 숫자 몇까지
        int M = Integer.parseInt(st.nextToken());   // 출력 개수

        arr = new int[M];
        visit = new boolean[N];
        dfs(N, M, 0);
        bw.write(sb.toString() + " ");
        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int N, int M, int depth) {
        if (M == depth) {
            for (int i : arr) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                arr[depth] = i + 1;
                dfs(N, M, depth + 1);
                visit[i] = false;
            }
        }
    }
}