[BOJ 15663/15664 c++]N과 M, set, backtracking

 

15663 set 풀이

set은 키의 중복 허용하지 않고 키값 정렬시킨다.

//참고 사이트 https://tooo1.tistory.com/327 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 9
using namespace std;


int N,M;
int num[MAX]; //input 
bool visited[MAX]={0,};
int arr[MAX];
set<vector<int>> s;

void Backtrack(int depth){//depth : depth이자 arr의 index 
	if(depth == M){
		vector<int> v;
		for(auto i = 0; i<M;i++){
			v.push_back(arr[i]);
		} 
		s.insert(v);		
		return;
	}
	
	for(int i = 0 ; i < N ;i++){
		if(visited[i]) continue;
		visited[i] = true;
		arr[depth] = num[i];
		Backtrack(depth+1);
		visited[i]=false;
	}	
}
 

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0 ; i<N; i++) cin>>num[i];
	sort(num,num+N);
	Backtrack(0);//depth 의미
	for(auto v : s){
		for(auto e : v){
			cout<<e<<" ";
		}
		cout<<"\n";
	}  

	
}

 

 

15664 set 풀이

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 9
using namespace std;

int N,M;
int num[MAX];
bool visited[MAX]={0,};
set<vector<int>> answer;
int arr[MAX];

void BackTrack(int depth){
	if(depth == M){
		
		vector<int> v;
		for(int i = 0; i < M ; i++){
			v.push_back(arr[i]);
		}
		sort(v.begin(),v.end());
		answer.insert(v);
		return;
	}

	for(int i = 0 ; i < N ;i++){
		if(visited[i]) continue;
		arr[depth] = num[i];
		visited[i] = true;
		BackTrack(depth+1);
		visited[i] = false;
	}	
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i= 0; i < N ;i++)cin>>num[i];
	
	sort(num,num+N);
	
	BackTrack(0);

	for(auto v : answer){
		for(int e : v){
			cout<<e<<" ";
		}
		cout<<"\n";
	}
	
	
	
}

15663 번과 비슷하게 set을 이용해 풀었다. 

 

15664 set 이용하지 않음

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 9
using namespace std;

int N,M;
int input[MAX];
bool visited[MAX]={0,};
int arr[MAX];

void BackTrack(int depth){
	if(depth == M){
		for(int i = 0 ; i < M ;i++){
			cout<<arr[i]<<" ";
		}
		cout<<"\n";
		return;
	}
	
	int flag = 0;  
	for(int i = 0 ; i < N ;i++){
		if(!visited[i] && flag != input[i]){
			if(depth){
				if(arr[depth-1] > input[i]) continue;
			}
			visited[i]=true;
			flag = arr[depth] = input[i];
			BackTrack(depth+1);
			visited[i]=false;
			
		}
	}


}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i= 0; i < N ;i++)cin>>input[i];
	
	sort(input,input+N);
	BackTrack(0);	
}

set을 이용하지 않으니 약간 헷갈렸다.

flag의 용도는 중복되는 숫자를 만들지 않기 위함이다.

이렇게 flag를 사용해서 중복 방지한다.

약간 헷갈린다. set을 사용하지 않고 15663 번도 풀어봐야겠다.