[C/C++] 백준 10974번 - 모든 순열

백준 10974번 모든 순열

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

 

백트래킹을 이용해서 풀었습니다. 8칸의 배열을 만들어놓고 방문하지 않은 곳들을 재귀를 이용해서 방문하고 방문한 후에는 true로 체크하여 똑같은 곳을 방문하지 않도록 했습니다. 처음 보면 잘 이해가 가지 않을수도 있는데 가지치기를 생각하면 쉽게 생각할 수 있습니다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
bool visited[8];
int v[8] = { 1,2,3,4,5,6,7,8 };
int arr[8];
void abc(int cnt) {
	if (cnt == n) {
		for (int x = 0; x < n; x++)
			cout << arr[x] << " ";
		cout << '\n';
		return;
	}
	for (int x = 0; x < n; x++) {
		if (!visited[x]) {
			visited[x] = true;
			arr[cnt] = v[x];
			abc(cnt + 1);
			visited[x] = 0;
		}
	}

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

	cin >> n;

	abc(0);
}