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

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

15649번: N과 M (1)

---

문제 풀이

 1. 1부터 N까지 자연수 중 중복 없이 M개 고른 수열을 구현하기 위해 visited 배열을 이용해 중복의 여부를 체크한다.

 2. dfs함수를 이용해서 모든 경우를 확인한다. 

 DFS (Depth-First Search) : 깊이 우선 탐색

Root 노드에서 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐사하는 방법 - 모든 노드를 확인할 때 유용

어떤 노드를 방문했는지 체크해야함 - 무한루프 방지!

느낀 점

 저번 문제를 기점으로 C에서 C++로 넘어가게 되었다. C에 비해서 너무 편해 후회감이 들었다. 

코드에 전혀 문제가 없는데 시간 초과가 발생하여 매우 당황했는데, 찾아보니 endl은 버퍼를 flush해서 "\n"보다 시간이 더 오래 걸린다는 점을 알게 되었다. 

지금 푸는 단계인 백트래킹은 언뜻 보면 브루트 포스와 비슷하다고 생각이 들었다. 찾아보니 다른 점이 명확해서 이번 단계에선 이 점을 잘 짚고 넘어가야 할 것 같다.

 백트래킹 : 이미 지나친 곳을 다시 돌아가서 다른 가능성을 시도

 브루트 포스 : 모든 경우의 수를 다 대입

코드

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

vector<int> v;
int arr[MAX];
bool visited[MAX];
int n, m;

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;
		visited[i] = true;
		v.push_back(arr[i]);
		dfs(cnt + 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);

	return 0;
}