백준 10974 모든 순열 c++ (순열)

문제 출처 : https://www.acmicpc.net/problem/10974

10974번: 모든 순열

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

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

알고리즘 분류

• 브루트포스 알고리즘

풀이

순열을 이용한 브루트포스 문제이다.

순열 알고리즘의 기본 문제이며, 조합과 더불어 dfs 알고리즘을 많이 이용한다.

nCr = n개의 리스트에서 r개를 고르는 조합

nPr = n개의 리스트에서 r개를 고르는 순열

조합은 1 2 3 == 3 2 1 이고,

순열은 1 2 3 != 3 2 1 이다.

즉 순열은 순서가 다르면 다른 요소라 판단하고,

조합은 순서가 달라도 같은 요소라 판단한다.

기본 문제라 풀이는 설명할 게 없다.

문제를 풀기 전, 순열, 조합 알고리즘에 대해 우선적으로 공부하길!

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
bool visited[9];

void permutation(int cnt,vector<int> result) {
	if (cnt == n) {
		for (int i = 0; i < cnt; i++) {
			cout << result[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		result[cnt] = i;
		permutation(cnt + 1,result);
		visited[i] = false;

	}
}

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

	vector<int> result(n);
	permutation(0,result);


	return 0;
}