알고리즘 : 백트래킹 (Back-tracking) + 조합, 순열 (C++ 구현)

백트래킹 (Back-tracking)

정답을 찾는 도중에 막히면 더 이상 깊이 들어가지 않고 이전 단계로 돌아가서 정답을 찾는 방법

 

깊이 우선 탐색 DFS는 가능한 모든 경로를 탐색한다. 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다. 

백트래킹은 지금 경로가 정답이 아닐 것 같다면 이전 단계로 돌아가므로 DFS보다 효율적이다. 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이 백트래킹이다.

 

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

 

 

백트래킹 예시

bool visited[20];
int n, r;
void dfs(int cnt, int idx) { // 현재까지 결과, 탐색 진행할 인덱스
    // 조건에 해당할 때 중기
    if (cnt == r) {
        for (int i = 0; i < n; i++)
        {
            if(visited[i]==1)
                cout << i << " ";
        }
        cout << '\n';
        return;
    }

    for (int i = idx; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(cnt + 1, i);
            visited[i] = false; // 다시 돌아갈 수 있도록
        }
    }
}

int main() {
    n = 4;
    r = 2;
    dfs(0, 0);
}

n개 중 순서를 고려하지 않고 r개를 선택하는 조합 코드이다. 자세한 코드 설명은 아래에서 하도록 하겠다.

 

 

1. 조합

 

가장 처음으로 뽑을 index가 정해지면 그 이후 전으로 돌아갈 필요가 없다. 화살표 방향이 오른쪽을 향하는 것이다. 

void dfs(int idx, int cnt) {
	if (cnt == k) {
		for (int i = 0; i < v.size(); i++)
		{
			if (visited[i] == 1)
				cout << v[i] << " ";
		}
		cout << '\n';
		return;
	}

	for (int i = idx; i < n; i++) // 선택될거 결정
	{
		if (visited[i] == 1) // 이미 방문
			continue;
		visited[i] = 1;
		dfs(i, cnt + 1);
		visited[i] = 0; // {1, 2, 5}이 끝났다면 {1, 3, 5}에서도 5가 선택될 수 있도록
	}
}
int main() {
	cin >> n >> k; // nCk = n개 중에 k 선택
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
	dfs(0, 0);
}

중복을 허용하지 않는 조합이다.

 

vector <int> v;
vector <int> temp;
int n, k;
void dfs(int idx, int cnt) {
	if (cnt == k) {
		for (int i = 0; i < temp.size(); i++)
		{
			cout << temp[i] << " ";
		}
		cout << '\n';
		return;
	}

	for (int i = idx; i < n; i++) // 선택될거 결정
	{
		temp.push_back(v[i]);
		dfs(i, cnt + 1);
		temp.pop_back(); // {1, 2, 3}이 끝났다면 {1, 2, 4}가 될 수 있도록
	}
}
int main() {
	cin >> n >> k; // nCk = n개 중에 k 선택
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
	dfs(0, 0);
}

중복조합에서는 visited 배열 없이 vector로만 구현하면 된다.

 

 

2. 순열

 

순열은 조합과 다르게 거꾸로 갈 수도 있다. 순서를 고려하기 때문이다. idx 변수가 필요하지 않는 것이다.

 

void dfs(int idx, int cnt) {
	if (cnt == k) {
		for (int i = 0; i < temp.size(); i++)
		{
			cout << temp[i] << " ";
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; i++) // 선택될거 결정
	{
		if (visited[i] == 1)
			continue;
		visited[i] = 1;
		temp.push_back(v[i]);
		dfs(i, cnt + 1);
		visited[i] = 0;
		temp.pop_back();
	}
}
int main() {
	cin >> n >> k; // nCk = n개 중에 k 선택
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
	dfs(0, 0);
}

여기서 visited를 없애면 중복 순열이 된다.

 

코드가 이해가 되지 않는다면 아래 티스토리를 읽어보는 걸 적극 추천한다! 정말 설명을 잘해두셨다. 사진도 여기에 있는 걸 참고하였다.

https://charles098.tistory.com/9

[C++] 순열과 조합 DFS로 구현해보기