[백준 15649번 / C++] N과 M (1)

DFS를 활용해서 완전탐색으로 풀어보자. 

 

#접근방법 

 

1. 먼저 n과 m을 입력 받은 후에 level 값을 파라미터 값으로 전달하면서 바로 dfs를 호출한다. 

2. level이 m 이 되었을 때는 지금까지 push_back 해서 모은 result값을 출력한다. 

3. 그렇지 않다면 1~n 만큼 반복문을 돌리면서 방문 처리되지 않았을 경우, 방문 처리 및 result값 추가하고 dfs를 호출

4. 호출해서 돌아온 후에는 방문처리를 false 하고 result 배열에 넣었던 값을 다시 빼준다. 

 

#include <iostream>
#include <vector>
using namespace std;
int n, m;
bool visited[10];
vector <int> result;
void dfs(int level) {
	if (level == m) {
		for (int x : result)cout << x << " ";
		cout << "\n";
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			result.push_back(i);
			dfs(level + 1);
			visited[i] = false;
			result.pop_back();
		}
	}
	return;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	dfs(0);
	return 0;
}

 

15649번: N과 M (1)