백준15650 - N과 M (2)

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

15650번: N과 M (2)

조합의 기초 문제이다. dfs를 이용하여 구현하였다. 현재 위치에서 그 다음 위치로 탐색할 수 있도록 for문을 구성하였다.

 

#include <iostream>
#include <vector>
using namespace std;

int m, n; //원소 m개중 n개를 뽑는다.
vector<bool> visit; //방문 여부
vector<int> v; //원소의 정보
vector<int> choose; //원하는 갯수만큼 고른 원소의 정보

//조합 구현
void com(int idx, int depth) {
	if (depth == n) { //원하는 갯수만큼 골랐으면 출력
		for (int i = 0; i < choose.size(); i++) {
			cout << choose[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = idx; i < v.size(); i++) {
		if (visit[i]) {
			continue;
		}
		visit[i] = true; //현재 원소 방문 처리
		choose.push_back(v[i]); //현재 원소 고른 항목에 넣기
		com(i, depth + 1); //재귀로 현재 원소부터 끝까지 탐색, 선택한 원소의 갯수는 한 개 늘려서 수행
		visit[i] = false; //현재 원소 방문 처리 하지 않음
		choose.pop_back(); //마지막에 고른 원소 삭제
	}
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		v.push_back(i + 1);
		visit.push_back(false);
	}
	com(0, 0); //현재 원소의 위치는 0번째이고 뽑은 원소의 갯수는 0개이다.
}