[알고리즘] 백트레킹

백트래킹이란?

해를 얻을 때까지 모든 경우의 수를 시도하는 알고리즘이다. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 이전으로 돌아가서 다른 규칙을 선택하여 다시 시도한다. 보통 DFS를 사용해서 탐색하면서 조건을 통해 필요 없는 부분을 쳐낸다.

 

백트래킹 예시

N-Queen 문제가 가장 대표적인데, 예시로 너무 많이 나와서 다른 문제를 준비해봤다.

N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

해결방법

해당 숫자를 골랐는지의 유무를 저장하는 visited 배열을 사용하여 1부터 고르지 않은 숫자를 찾아 arr 배열에 저장한다. 이때 배열의 인덱스는 고른 숫자의 개수(cnt)이다. cnt는 백트레킹 함수의 파라미터가 되며, 고른 숫자를 배열에 저장하면 backtracking(cnt+1)을 수행하고 이후에 해당 숫자를 고르지 않았음으로 바꿔야 다른 경우의 수도 고려할 수 있다. 마지막으로 cnt == M이 되면, arr 배열을 출력해주면 된다.

 

코드

#include<iostream>

using namespace std;

int n, m;
int arr[9];
bool visited[9];

void backtracking(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (visited[i])
			continue;
		visited[i] = true;
		arr[cnt] = i;
		backtracking(cnt + 1);
		visited[i] = false;
	}
}

int main() {
	cin >> n >> m;

	backtracking(0);

	return 0;
}