[백준 15650] N과 M (2)

● 문제 : 백준 15650번 : N과 M (2)

15650번: N과 M (2)

 

● 알고리즘

- 재귀함수

- 백트래킹

[백트래킹]

 

● 문제 풀이

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

[백준 15649] N과 M (1)

이전 글인 백준 15649번 N과 M (1) 문제가 순열을 구하는 것이라면, 이 문제는 조합을 구하는 것이다. 순열과 조합의 차이는 순서를 생각하느냐이다. 순열에서 (1,2)와 (2,1)은 다른 수열이지만, 조합에서는 같은 수열이라고 보는 것이다. 따라서, DFS 함수에 start라는 매개변수를 추가하여 현재 숫자보다 작은 값은 탐색하지 않도록 한다. 

예를 들어, N=3, M=2라고 하면 

1) DFS(1,0)

2) visit[1]=1, arr.push_back(1) -> arr={1}

3) DFS(2,1)

4) start=2

visit[2]=1, arr.push_back(2) -> arr={1,2}

5) DFS(3,2)

cnt==M(2)이므로 1,2 출력 후 재귀함수 종료 -> 4)로 돌아감

6) visit[2]=0, arr.pop_back() -> arr={1}

7) visit[3]=0, arr.push_back(3) -> arr={1,3}

8) DFS(4,2)

cnt==M(2)이므로 1,3 출력 후 재귀함수 종료 -> 7)로 돌아감

9) visit[3]=0, arr.pop_back() -> arr={1}

10) for문 끝났으므로 재귀함수 종료 -> 2)로 돌아감

11) visit[1]=0, arr.pop_back() -> arr={}

12) visit[2]=1, arr.push_back(2) -> arr={2}

13) DFS(3,1)

14) start=3

visit[3]=1, arr.push_back(3) -> arr={2,3}

15) DFS(4,2)

cnt==M(2)이므로 2,3 출력 후 재귀함수 종료 -> 14)로 돌아감

16) visit[3]=0, arr.pop_back() -> arr={2}

17) for문 끝났으므로 재귀함수 종료 -> 12)로 돌아감

18) visit[2]=0, arr.pop_back() -> arr={}

19) visit[3]=1, arr.push_back(3) -> arr={3}

20) DFS(4,1)

21) start=4 가 N(3)보다 크므로 재귀함수 종료 -> 19)로 돌아감

22) visit[3]=0, arr.pop_back() -> arr={}

23) 종료

 

● 코드

#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 start, int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = start; i <= N; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			arr.push_back(i);
			DFS(i + 1, 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(1, 0);
	return 0;
}