[C++] 백준 15650번 : N과 M (2)

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

15650번: N과 M (2)

---

문제 풀이

 이전 문제와 다른 점이 고른 수열이 오름차순이기 때문에 구현한 DFS에 추가적인 조건을 넣는다.

조건(1) : 벡터 v의 사이즈가 0이면 비교 없이 그냥 바로 값을 대입한다.

조건(2) : v의 사이즈가 0이 아니면 이전 값과 추가할 값을 비교해서 값을 대입한다. 이전 idx의 값이 추가할 값보다 크다면 다음으로 넘어간다.

느낀점

 더 나은 코드의 구현을 위해서 다른 분들의 코드를 검색해봤다. 조건문으로 따질 필요 없이 재귀 호출 시 이전 idx 값을 따지지 않도록 구현하면 되던 것이었다... T.T

 

이전 코드

#include <iostream>
#include <vector>
#define MAX 9
using namespace std;

int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
vector<int>v;
int n, m, k = 0;

void DFS(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < v.size();i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 0; i < n;i++) {
		if (visited[i]) continue;
		if (v.size() == 0) {
			visited[i] = true;
			v.push_back(arr[i]);
			BFS(cnt + 1);
			v.pop_back();
			visited[i] = false;
		}
		else {
			if (v[k] < arr[i]) {
				visited[i] = true;
				v.push_back(arr[i]); k++;
				BFS(cnt + 1);
				v.pop_back(); k--;
				visited[i] = false;
			}
			else continue;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n;i++) {
		arr[i] = i + 1;
		visited[i] = false;
	}
	DFS(0);
}

발전된 코드

#include <iostream>
#include <vector>
#define MAX 9
using namespace std;

int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
vector<int>v;
int n, m;

void DFS(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < v.size();i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = idx; i < n;i++) {
		if (visited[i]) continue;
		visited[i] = true;
		v.push_back(arr[i]);
		DFS(cnt + 1, i + 1);
		v.pop_back();
		visited[i] = false;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n;i++) {
		arr[i] = i + 1;
		visited[i] = false;
	}
	DFS(0, 0);
}