백준 15654번 - N과 M(5)

N과 M(5)

N과 M은 백준에 시리즈물로 쭈루루룩 있다.
백트래킹의 연습을 하기 위한 문제이다.

번호가 올라갈 때 마다 조건이 하나씩 추가되고 하는데
이번문제는 숫자가 작은 순서대로 나오라는 것이다.

그런데 사실 생각을 차분히 해보면
순회하면서 백트래킹을 한다고 했을 때
출력값이 정렬되려면 어떻게 해야 할까?

답은 간단하다.
정렬된 상황에서 백트래킹을 돌리면 된다.

이거 말고는 딱히 다른 아이디어에 대해
언급하기 힘든 문제이다.

딱히 언급할 게 많지 않는 난이도의 문제

코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n,m;
vector<int> nums;
vector<int> v;
bool visited[8]={0};
void printVector();
void dfs(int );
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		int k; cin>>k;
		nums.push_back(k);
	}
	sort(nums.begin(),nums.end());
	for(int i=0;i<nums.size();i++){
		dfs(i);
	}
	return 0;
}
void printVector(){
	for(auto x : v){
		cout<<x<<" ";
	}
	cout<<'\n';
}
void dfs(int i){
	if(v.size()>=nums.size()) return;
	if(visited[i]) return;
	visited[i]=true;
	v.push_back(nums[i]);
	if(v.size()==m){
		printVector();
	}else{
		for(int j=0;j<nums.size();j++){
			if(i==j) continue;
			else dfs(j);
		}
	}
	v.pop_back();
	visited[i]=false;
	return;
}