[BOJ 15649] N과 M(1)

[문제 출처]

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

 

1부터 N까지 자연수중 길이가 M인 순열을 출력하는 문제입니다.

 

[순열 ?]

 순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식입니다. 즉 순서가 존재하는 열인 것이죠.

c++기준 next_permutation / prev_permutation과 같은 STL함수를 통해 쉽게 구현할 수 있습니다. 

 

[문제풀이]

 완전 탐색을 통해 문제를 풀이합니다. DFS방식으로 basecase조건 충족시 출력을 하고 함수에서 나오는 방법입니다. 이때 visit배열로 방문여부를 체크하여 중복 값이 사용되는 것, 다시말해 같은 수를 여러번 고르는 경우를 방지하면 됩니다.

 

[소스코드]

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> v;
bool visit[9];
void solve(int cnt) {
	if (cnt == m) {
		for (int i=0; i<v.size(); i++) cout<<v[i]<<" ";
		cout<<"\n";
		return;
	}
	
	for (int i=1; i<=n; i++) {
		if (visit[i]) continue;
		visit[i] = 1;
		v.push_back(i);
		solve(cnt+1);
		visit[i] = 0;
		v.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	solve(0);
	return 0;	
}