[백준 BOJ][C++]15650번 N과 M(2) 풀이: 브루트 포스 & DFS

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

15650번: N과 M (2)

 

 이 문제는 15649번 N과 M(1) 풀이와 매우 유사합니다. 

(풀이: https://iridescent-zeal.tistory.com/86)

 

 하나만 바꾸어 주면 되는데요!

 

 dfs 함수에 현재 노드의 수를 나타내는 인자를 추가하여 해당 노드 보다 큰 수에 대해서만 자식 노드를 탐색하면 간단하게 풀립니다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<cmath>

using namespace std;

int n, m;
bool visit[9] = { false, };
int arr[9];

void dfs(int num, int depth) {

	if (depth == m - 1) {
		for (int i = 0; i < m; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");

		return;
	}

	for (int i = num + 1; i <= n; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[depth + 1] = i;
			dfs(i, depth + 1);
			visit[i] = false;
		}
	}

}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		visit[i] = true;
		arr[0] = i;
		dfs(i, 0);
		visit[i] = false;
	}

	return 0;
}