N과 M (9)

문제

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

해당 문제는 입력으로 주어진 n개의 숫자에서 m개를 골라 오름차순으로 출력하는 문제로 생각했다.

이를 DFS 탐색을 통해 구현하기 위한 가장 핵심적인 아이디어로
1) 트리의 같은 레벨에서 이미 탐색된(중복되는) 숫자는 더이상 탐색하지 않는 것이고,
2) 트리 전체를 순회할 때도 이미 탐색한 숫자는 탐색하지 않는 것이다.

이를 위해 같은 레벨에서 탐색여부를 나타내는 level_check 배열과, DFS 순회과정에서 탐색 숫자 여부를 나타내는 check 배열을 선언했다.

참고로, 위의 과정 전에 오름차순 출력을 위해 입력 숫자를 받은 vector를 sort 함수를 통해 정렬하였다.

이를 통해 같은 레벨에서 이미 탐색한(중복되는) 숫자를 순회하는 경우와 이미 이전 레벨에서 순회한 숫자를 순회하는 경우를 제거할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int n, m;
int res[10], check[10];
vector<int> input_num;

void DFS(int L) {
	int level_check[10001] = { 0, };

	if (L == m) {
		for (int j = 0; j < m; j++) {
			cout << res[j] << ' ';
		}
		cout << "\n";
	}

	else {	

		for (int i = 0; i < input_num.size(); i++) {
			
			if (check[i] == 0 && level_check[input_num[i]] == 0) {
				res[L] = input_num[i];
				check[i] = 1;
				level_check[input_num[i]] = 1;
				DFS(L + 1);
				check[i] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	cin >> n >> m;

	int temp;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		input_num.push_back(temp);
	}

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

	DFS(0);
	return 0;
}