DFS를 활용한 순열

 이전에 dfs를 활용한 조합을 봤습니다. 순열도 비슷한 방식으로 백트래킹을 사용합니다.

조합과 순열의 가장 큰 차이는 순서입니다. 조합은 1 2 3, 1 3 2 가 같지만 순열은 다르다고 봅니다.

때문에 조합은 idx라는 인수를 갱신하면서 1 2 3 에서 2개를 뽑는다고 치면 1 2, 1 3 하고 끝! 이었습니다. 

그러나 순열은 순서를 중요시 생각하기 때문에 2 부터 시작하는 순서도 2 1 가 나와줘야합니다. 

이를 이해해야합니다.

 

#include<iostream>
#include<vector>
#define MAX 4
using namespace std;

vector<int> num;
vector<int> result;

bool visited[5] = { false, };

void dfs(int cnt) {
	if (cnt == MAX) {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = 0; i < 5; i++) {
		if (visited[i] == true)
			continue;
		visited[i] = true;
		result.push_back(num[i]);
		dfs(cnt + 1);
		result.pop_back();
		visited[i] = false;
	}
}

int main() {
	num.push_back(1);
	num.push_back(2);
	num.push_back(3);
	num.push_back(4);
	num.push_back(5);

	dfs(0);
}

 

조합과 같지만 idx가 사라졌고 백트래킹 할때마다 0부터 끝까지 한번 더 확인함을 알 수 있습니다.