[알고리즘] 순열

순열은 DFS로 풀 수 있는데 코드만 보면 감이 아예 안잡힌다
 
보통 DFS 떠올리면 그래프나 트리를 생각하고 적용하는데 
순열 조합은 그래프 트리로 생각하면 안된다
 

배열 내에서 DFS를 쓴다고 생각해야함

 
보통 DFS는 재귀 or stack + visited 가 필요한데 여기서도 똑같다.
적용되는 자료구조가 vector일뿐

---

#include <iostream>
#include <vector>
#define SIZE 10

using namespace std;

bool visited[SIZE];
int arr[SIZE];
vector<int> ans;

int N, M;

void print() {
	for (int i = 0; i < M; i++) cout << ans[i] << " ";
	cout << "\n";
}

void DFS(int cnt) {
	// cnt가 총 원소 개수면 종료
    	// 순열 1개의 끝
	if (cnt == M) {
		print();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			visited[i] = true;
			ans.push_back(arr[i]);
			DFS(cnt + 1);
			ans.pop_back();
			visited[i] = false;
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) arr[i] = i;

	DFS(0);
	return 0;
}

---

다음은 DFS(0)이 시작되고 1을 들어갔을 경우의 그림이다

[1]
cnt 변수가 전역변수가 아님. 그러니까 각 DFS 마다 매개변수로 받은 cnt값이 있음. 따라서 return할때 cnt--를 안해줘도 됨. 왜냐하면 return 을 받는( 그 전 dfs)는 자기만의 cnt값을 가지고 있기 때문. cnt+1로 자신이 재귀호출하는 또 다른 dfs함수로 넘겨준 것 뿐임
 
근데 이게 사실 전역변수로 써도 됨. return할때마다 cnt--하면 되긴함.
근데 일단 그냥 매개변수로 넘기는게 더 편함
 
[2]
DFS 는 for(int i=0;i<N;i++) 문 안에 있음
즉 최대 N개(배열 원소 수) 만큼 호출이 가능하고 최소 0개까지 호출가능.
 
이때 내 안에서 또 다른 재귀호출을 하냐 마냐는 visited[i] 로 결정됨
 
[3]
visited는 전역변수
visited[i] = false 해주는 이유가 그 다음 i번째에서도 그 전 i번째 원소를 선택할 수 있게끔 해주기 위해서임.
 
왜냐하면 순열이니까
 
2 3 이랑 3 2 랑 다른거니까
 
2가 재귀호출로 3선택했다고 3이 재귀호출로 2 선택 못하게 하면 안되니까

 

[4]

ans도 전역변수로 되어있는데

ans도 매개변수로 넘겨줘도 되긴하다

---

 
참고로 좀 멀리서보면 DFS안 for문이 대칭구조이다
 
이유는 추가한걸 뺌으로써 다음 꺼로 넘어가기전에 다시 원상태로 돌려놓고 dfs로 전달해야하기 때문