백트래킹이란?
백트래킹은 모든 경우의 수를 고려하는 알고리즘이다. 하지만 완전 탐색과는 다르게 조건이 있어, 무작정 경우의 수를 파악하기 보다는 가능성 있는 경우를 탐색하고 가능성이 아예 없는 경우 제외를 하게 된다. 따라서 단순하게 다중 for 문을 이용하는 전체 탐색보다는 효율적이고 빠르게 탐색이 가능하다.
위와 같은 트리가 존재할 때, D 노드가 조건에 부합하지 않는다고 가정해보자. 완전 탐색을 진행하게 된다면 노드가 조건에 부합하지 않더라도 안쪽까지 파고 들어 F, G 까지 확인을 하게 될 것이다. 하지만 백트래킹의 경우에는 D 노드가 조건에 부합하지 않는다면 굳이 F, G 까지 내려가지 않고 다시 B로 돌아와 유망한 노드를 탐색하게 되기 때문에 불필요한 과정을 줄여 더 효율적이라고 볼 수 있다.
구현 방법
일반적으로 dfs 혹은 bfs 알고리즘을 사용하여 구현하게 된다. 하지만, 백트래킹 특성 상 다음 노드가 유망하지 않다면 이전 노드로 돌아와야 하는 경우가 많기 때문에 bfs 보다는 dfs을 이용한 구현이 더 낫다. dfs을 사용하면 안되는 경우가 있다고 하는데 아직 겪어보지 못했기 때문에 겪게 된다면 수정을 할 생각이다.
백트래킹의 대표적인 문제는 N-Queen 문제가 있다.(백준 9663번)
N-Queen 문제를 모르는 분들을 위해 간단히 설명을 진행하자면
N X N 크기의 체스판에서 퀸들이 서로 공격할 수 없게 놓을 수 있는 경우의 수를 세는 문제이다.
별표를 퀸이라고 생각하였을 때, 체스에서 퀸은 상하좌우대각 모든 방향으로 이동이 가능하다. 그렇다면 2번째 줄에서 퀸이 놓일 수 있는 곳은 3, 4, 5, 6 4개의 경우가 가능하다. 즉, 1, 2 번의 경우에는 놓을 수 없기 때문에 이러한 경우의 수는 유망하지 않다고 판단하여 3번 칸에 2번째 퀸을 놓는 것으로 시작하여 다음 탐색을 진행하게 된다.
조금 더 쉬운 문제로는 백준 15654번 N과 M(5) 문제가 있다.
문제를 확인해보면, 숫자의 개수와 조합되어야 할 수가 주어진다.
2번 째 예제를 확인해보았을 때, 숫자가 4개 들어왔기 때문에 완전탐색으로 진행하게 된다면
11, 17, 18, 19, 71, 77, 78, 79, 81, 87, 88, 89, 91, 97, 98, 99 의 N^2 개의 수를 만들고 11, 77, 88, 99을 지우는 과정을 추가해야 한다.
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static List<Integer> numbers;
static boolean[] visited;
static int[] result;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
numbers = new ArrayList<>();
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
numbers.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(numbers);
visited = new boolean[N];
result = new int[M];
dfs(0);
System.out.print(sb);
}
public static void dfs(int depth) {
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(result[i]).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
result[depth] = numbers.get(i);
dfs(depth + 1);
visited[i] = false;
}
}
}
}이 코드에서 아래쪽 dfs 부분을 확인하게 되면, visited 를 true로 만들고 재귀가 끝나게 된다면 다시 false로 만드는 과정을 통해서, 한 번 사용된 숫자를 다음번에 다시 사용할 수 있도록 초기화를 해주고 있다.
이러한 초기화 과정이 없다면, 한 번 사용된 숫자는 다음번에 다시 사용될 수 없기 때문에 유망한 모든 조합을 탐색할 수 없게 되고, 앞서 말했듯이 유망하지 않다면 이전 상태로 복원을 해야하기 때문에 초기화를 하는 것이 중요하다고 한다.
사실 재귀와 백트래킹 등에 대한 부분은 혼자 공부하면서 머리속으로 전체적인 흐름을 생각하기에 아직 어려워서 정리를 해보았다. 알고리즘에 점점 익숙해져가는 내가 되었으면 좋겠다..!
댓글