[백준 10974] 모든 순열 C++

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

10974번: 모든 순열

문제 : N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

입력 : 첫째 줄에 N(1 <= N <= 8)이 주어진다

 

출력 : 첫째 줄부터 N! 개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

풀이

void go(int depth) {

	if (depth == n) {


		cal_max();

		return;
	}


	for (int i = 0; i < n; i++) {

		if (check[i]) continue;

		check[i] = true;
		selected[depth] = a[i];
		go(depth + 1);
		check[i] = false;
	}


	
}
void solution() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	go(0);


	cout << result << '\n';
	

}

이 문제는 중복되지는 않지만 순서에 상관없이 경우의 수를 구하는 문제입니다.

따라서, 중복만 되지 않게 check배열로 똑같은 수를 출력하지 않도록 사전에 방지하고, 

구할 수 있는 모든 경우의 수를 다 구하면 됩니다.

예를 들어, 1, 2, 3을 위의 논리로 풀게 되면 (1, 2, ,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 사전순으로 출력하게됩니다.

 

 

#include <iostream>

using namespace std;

#define MAX 8 + 1

int n;
int a[MAX];
int ans[MAX];
bool check[MAX];


void print() {


	for (int i = 0; i < n; i++) {
		cout << ans[i] << ' ';
	}
	cout << '\n';
}
void go(int depth) {

	if (depth == n) {

		print();

		return;
	}

	for (int i = 0; i < n; i++) {

		if (check[i]) continue;

		ans[depth] = a[i];
		check[i] = true;
		go(depth + 1);
		check[i] = false;

	}
}

void solution() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		a[i] = i + 1;
	}

	
	go(0);

}
int main() {


	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	//freopen("Input.txt", "r", stdin);

	solution();


	return 0;
}

 

위의 코드로 풀게되면 됩니다.