boj-15663 N과 M (9)

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

문제 소개

N개의 자연수 중 M개를 고른 수열을 모두 구한다.

수열은 사전 순으로 증가하는 순서로 출력한다.

중복된 원소가 있을 수 있다.

문제 풀이

먼저 n개의 수를 입력받아 vector arr에 저장하고 sort()로 정렬한다.

방법 1

next_permutation()을 이용하여 풀이하였다.

수열 맨 앞의 m개 원소만으로 vector를 만든 후 set에 추가하여 수열의 중복을 피하였다.

방법 2

백트래킹 방식으로 풀이하였다.

current의 길이가 m이 될 때까지 재귀적으로 arr를 탐색하며 원소를 current에 추가한다.

arr를 탐색할 때에는 bool원소를 가지는 vector인 valid를 사용하여 이미 추가된 원소인지 아닌지 확인한다.

추가적으로 같은 원소가 여러 개 존재할 경우에 대비하여 함수 dfs()의 현재 depth에서 마지막으로 current에 추가했던 원소를 기억하는 변수 last가 존재한다.

last는 같은 수열을 여러 번 중복해서 출력하는 것을 방지한다.

코드

방법 1

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

int n, m;
std::vector<int> arr;
std::set<std::vector<int>> result;  // 수열의 중복을 방지하기 위한 set

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		arr.push_back(t);
	}
	sort(arr.begin(), arr.end());

	do {
        // m개의 원소만 vector에 담아 result에 추가
		vector<int> temp;
		for (int i = 0; i < m; i++) {
			temp.push_back(arr[i]);
		}
		result.insert(temp);
	} while (next_permutation(arr.begin(), arr.end()));

    // result 내의 수열을 차례로 출력
	for (set<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {
		for (int i = 0; i < (*it).size(); i++) {
			cout << (*it)[i] << ' ';
		}
	cout << '\n';
	}

	return 0;
}

방법 2

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

int n, m;
std::vector<int> arr;
std::vector<int> current;

void dfs(int x, int cnt, std::vector<bool>& valid) {
	if (cnt == m) {
		for (int& t : current) {
			std::cout << t << ' ';
		}
		std::cout << '\n';
		return;
	}

	int last = 0;
	for (int i = 0; i < n; i++) {
        // 사용된 적이 없는 원소이면서 해당 depth에서 사용한 적이 없는 값인 경우에만 추가
		if (valid[i] && last != arr[i]) {
			last = arr[i];
			current.push_back(arr[i]);
			valid[i] = false;

			dfs(i, cnt + 1, valid);

			valid[i] = true;
			current.pop_back();
		}
		else {
			continue;
		}
	}
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		arr.push_back(t);
	}
	sort(arr.begin(), arr.end());

	vector<bool> valid(n, true);        // 각 원소가 current에 추가 가능한지 확인하는 vector
	dfs(0, 0, valid);

	return 0;
}