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

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

예제 입력	예제 출력
3	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

---

풀이

#include <iostream>
using namespace std;

int N;
int result[9];
bool check[9] = { false };

void dfs(int dth) {
	if (dth == N) {
		for (int i = 0; i < N; i++) 
			cout << result[i] << ' ';
		cout << '\n';

		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!check[i]) {
			result[dth] = i;

			check[i] = true;
			dfs(dth + 1);
			check[i] = false;
		}
	}
}

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

	cin >> N;

	dfs(0);

	return 0;
}

백트래킹으로 문제를 풀었다.