백트래킹
백트래킹은 해가 될 수 있는 경로에 대해 탐색을 진행하다가 해가 아니라는 것을 알게 되면 더 이상 탐색을 진행하지 않고 종료한 뒤 다른 경로에 대해 탐색하여 해를 찾는 방법이다.
백트래킹의 개념을 잡을 때 백준에 있는 N과 M시리즈를 풀어보면 도움이 많이 된다. 그 중 첫 번째 문제를 가지고 설명을 진행하며 백트래킹에 대한 개념을 이해해보도록 하자.
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
문제의 내용 자체도 길지 않으나 요약하면 1~N까지의 수 중 중복 없이 길이가 M인 수열을 모두 찾아 출력하는 것이다.
코드를 보며 설명을 진행하려고 한다.
#include <iostream>
using namespace std;
int N, M; // 입력 값
int arr[10]; // 담아놓을 배열
bool visit[10]; // 담았는지 확인
// 백트래킹
void backtrack(int k) {
if (k == M) { // M개를 뽑으면
for (int i = 0; i < k; i++) { // 뽑은 순서대로 출력
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= N; i++) { // 순서대로
if (visit[i] == false) { // 뽑혀있지 않으면
visit[i] = true; // 뽑고
arr[k] = i; // 저장한 뒤
backtrack(k + 1); // 다음으로 진행
visit[i] = false; // 끝나면 다시 넣어준다.
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
backtrack(0);
return 0;
}
그다지 길지 않은 코드지만 재귀함수를 이용하기 때문에 이해하는데 어려움이 있다. 백트래킹을 구현하는데 필요한 지식으로는 깊이 우선 탐색(DFS), 재귀 가 필요하다.
백트래킹은 깊이 우선 탐색과 동일한 방식으로 진행(재귀적인 진행도 가능)하지만 해가 아니라는 것을 알게 되면 중간에 멈춘다는 차이점이 있다.
bool visit[10] : 1부터 N까지 수가 하나씩 있기 때문에 중복으로 뽑을 수 없고 뽑았는지를 확인하기 위한 bool 타입 배열 visit을 선언해주었다.
int arr[10] : arr은 현재까지 뽑은 수를 저장해두기 위해 선언해놓은 배열이다.
void backtracking(int k) : backtracking 함수의 인자 k는 현재까지 뽑은 수의 개수를 의미하고 이것이 문제에서 주어진 M과 같다면 뽑는 것을 종료하고 현재까지 뽑은 숫자들을 출력해준다.
backtracking함수는 재귀적으로 구현할 것이기 때문에 base condition이 필요하고 if(k==M)이 base condition이 된다.
18~23라인이 이해하기 어려운 부분인데, 1부터 차례차례 확인하며 뽑아보는데 만약 뽑혀있지 않다면(visit[i]가 false라면 뽑혀있지 않은 상태이다.) 해당 숫자를 뽑고(arr배열에 추가), 뽑았다는 표시(visit[i]를 true로 바꿔줌)를 해준 뒤, 뽑은 개수를 하나 늘려(k를 k+1로 교체) 다시 backtracking함수를 호출한다.
