[백준알고리즘] 10974번: 모든 순열 -C++

[백준알고리즘] 10974번: 모든 순열 -C++

10974번: 모든 순열 (acmicpc.net)

10974번: 모든 순열

가능한 순열을 오름차순으로 출력하는 문제다. 처음에는 순열을 만드는 STL 라이브러리를 사용하지 않고 문제를 풀었고, 이후 해당 기능의 라이브러리가 있을 것 같아 찾아서 적용해봤다. 두 경우 모두 통과했고, 아래에 순서대로 작성해놨다. 간단한 문제라서 길진 않다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

1. 직접 구현

직접 순열을 만들고 출력하는 함수를 만들어주었다. DFS로 동작하면서 브루트포스(완전 탐색)를 시도해서 문제를 풀었다.

 

길이가 \(n\)이 되는 순간 생성된 순열을 출력해주었다. 그러면서 각 수를 더해보고 뒤에서 빼보면서 stack과 함께 순열을 만들었다.

 

만들어야 할 순열의 범위도 작았고, 간단히 구할 수 있었던 문제였기 때문에 쉽게 DFS로 풀 수 있었다.

 

아래의 printPermutation 함수가 직접 순열을 만들고 출력하는 함수다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void printPermutation(int step, std::vector<bool>& visit, std::vector<int>& permutation)
{
	if (step == 0)
	{
		for (auto p : permutation)
			std::cout << p << ' ';
		std::cout << '\n';
		return;
	}

	int length = visit.size();
	for (int i = 1; i < length; i++)
	{
		if (visit[i])
			continue;

		visit[i] = true;
		permutation.push_back(i);
		printPermutation(step - 1, visit, permutation);
		visit[i] = false;
		permutation.pop_back();
	}
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<bool> visit(n + 1, false);
	std::vector<int> permutation;

	printPermutation(n, visit, permutation);
}

 

2. std::next_permutation 사용

순열을 만드는 라이브러리가 존재할 것으로 생각하고 찾아봤다. <algorithm> 헤더에 포함되어있는 next_permutation과 prev_permutation이 그 역할을 한다는 것을 찾았다.

 

next_permutation은 주어진 순열(벡터)의 다음 순열의 형태로 순열을 바꿔주는 함수다.

 

따라서 각 단계마다 출력하는 함수만 만들어주면 되며 계속해서 순열을 만들어주면 된다. 더 이상 만들 순열이 없다면, 종료된다. (결과로 나온 순열이 원본 순열보다 크다면 true를 return 하며, 결과로 나온 순열이 원본 순열보다 작다면 false를 return 한다고 한다.)

 

역시나 직접구현해주는 것보다 간단하게 구현할 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> permutation(n);
	for (int i = 1; i <= n; i++)
		permutation[i - 1] = i;

	do {
		for (auto p : permutation)
			std::cout << p << ' ';
		std::cout << '\n';
	} while (std::next_permutation(permutation.begin(), permutation.end()));
}