[백준 15651] N과 M (3)

● 문제 : 백준 15651번 : N과 M (3)

15651번: N과 M (3)

 

● 알고리즘

- 재귀함수

- 백트래킹

[백트래킹]

 

● 문제 풀이

백준 15649번 N과 M (1) 코드에서 조금만 수정하면 된다.

[백준 15649] N과 M (1)

백준 15649번 N과 M (1) 문제가 중복을 허용하지 않는 순열을 구하는 것이라면, 이 문제는 중복을 허용하는 순열을 구하는 것이다. (1,1)과 같은 수열도 허용한다는 것이다. 따라서, 백트래킹을 위한 조건인 방문했는지를 검사하는 단계가 필요없어진다. 그러므로 N과 M (1) 코드에서 if (visit[i] == 0) 구문만 없애주면 된다.

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		visit[i] = 1;
		arr.push_back(i);
		DFS(cnt + 1);
		visit[i] = 0;
		arr.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(0);
	return 0;
}