[백준 / C++] 15654 N 과 M (5) - 백트래킹

백준 15654번 N과 M (5) 문제 

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

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

예제 입력 1 

3 1
4 5 2

예제 출력 1 

2
4
5

예제 입력 2 

4 2
9 8 7 1

예제 출력 2 

1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

 

---

 

N과 M 문제 풀이

 

이 문제를 풀기 위해선 먼저 백트래킹에 대해 알아야한다. 

 

백트래킹이란?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

 

따라서, 백트래킹을 사용하는 상황은 모든 경우를 탐색해야하고, 경우의 수가 많지 않을 때 사용하기 적합하다. 

N과 M같이 (1 ≤ M ≤ N ≤ 8) 일 때 유용하다.

 

백트래킹은 모든 경우를 탐색해야 하기 때문에 재귀를 사용해야 한다. 

 

---

N과 M (5) 전체 코드 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int number[100001] = { 0 };
int n, m;
bool check[100001] = { 0 };
int arr[9];

void backtra(int num) {

	if (num == m) {
		for (int i = 1; i <= m; i++) {
			cout << arr[i] << " ";
		}
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!check[i]) {
			arr[num + 1] = number[i];
			check[i] = 1;
			backtra(num + 1);
			check[i] = 0;
		}
	}
}

int main() {
	

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int ex;
		cin >> ex;
		number[i] = ex;
	}
	sort(number, number+n);
	backtra(0);
}