백준 10974: 모든 순열

문제 요약

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

문제 분류

• 브루트포스 알고리즘
• 백트래킹

문제 풀이

N까지의 수열을 N번 탐색하여 출력하면 된다. 중복이 불가하므로 사용한 수는 bool타입의 used[]로 사용여부를 저장하고, 사용되었다면 해당 탐색을 종료한다.

탐색을 N번 했다면, 지금까지 저장된 res배열을 전부 출력하고 돌아간다. 함수의 시작에는 해당 수를 사용했다고 used[val]를 true로 하고, 끝에는 false로 만들어 회수해주어야 한다.

N과 M문제와 많이 닮아있어서 해당 문제도 풀어보면 좋을 것 같다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int res[9], n;
bool used[9];

void dfs(int idx, int val) {
	if (used[val]) return;
	res[idx] = val;
	used[val] = true;
	if (idx + 1 == n) {
		for (int i = 0; i < n; i++)
			printf("%d ", res[i]);
		printf("\n");
		used[val] = false;
		return;
	}
	for (int i = 1; i <= n; i++)
		dfs(idx + 1, i);
	used[val] = false;
	
}

int main()
{
	cin >> n;
	
	for (int i = 1; i <= n; i++)
		dfs(0, i);
	return 0;
}