백준15663 - N과 M(9)

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

15663번: N과 M (9)

수열문제인데 굉장히 재밌는 문제였다. 중복된 원소를 제거해야 되었다. 나는 우선적으로 입력한 원소들을 오름차순으로 정렬 하였다. 그런 후 각각의 케이스마다 처음 선택한 원소를 저장하여 이전에 사용했던 원소인지 검사한다. 이전에 사용했던 원소이면 건너뛰고 사용하지 않은 원소이면 탐색을 시작한다. 방문한 곳을 재방문하지 않도록 dfs를 사용하여 탐색하였다. 중요한 점은 전에 출력했던 원소를 출력하지 않도록 set을 이용하여 중복 원소를 걸러주었다. 이런식으로 입력한 원소를 처음부터 끝까지 반복한다.

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
using namespace std;

int n, m; //n개 중 m개 고르기
int num; //숫자 입력
vector<int> v; //숫자 입력
vector<int> ans; //출력할 원소
vector<bool> visit; //입력한 숫자 방문 여부
set<vector<int>> st; //출력한 원소를 저장
int before = 0; //전에 사용한 변수 저장

void func(int x) {
	visit[x] = true;
	ans.push_back(v[x]);
	if (ans.size() == m) {
		if (st.find(ans) == st.end()) { //전에 없던 원소이면
			for (int i = 0; i < ans.size(); i++) { //출력
				cout << ans[i] << ' ';
			}
			cout << '\n';
			st.insert(ans); //출력한 원소를 set에 삽입
			return;
		}
	}
	for (int i = 0; i < v.size(); i++) {
		if (!visit[i]) { //i번째 원소에 방문하지 않았으면
			func(i); //i번째에서 dfs시작
			ans.pop_back(); //ans에서 맨 뒤에 원소 삭제
			visit[i] = false; //i번째 원소를 미방문 처리
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
		visit.push_back(false);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		if (before == v[i]) { //전에 사용했던 원소이면
			continue; //무시
		}
		else { //전에 사용하지 않은 원소이면
			before = v[i]; //갱신
		}
		for (int j = 0; j < visit.size(); j++) { //모든 숫자 미방문 처리
			visit[j] = false;
		}
		ans.clear(); //답 삭제
		func(i); //i번째 탐색 시작
	}
}