15649) N과 M (1) c++

문제 ) www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

풀이 ) 

조합의 개수를 구하는 문제로 dfs 를 활용하여 풀 수 있다.

N까지의 숫자를 인덱스로 가지는 bool 형 배열 visited 를 이용해서 해당 숫자를 뽑았는지 유무를 저장한다.

숫자를 앞에서부터 한개씩 뽑아가면서 visited 가 M개만큼 true 가 되면 출력해주는 재귀함수를 사용한다.

 

 

코드 ) 

#include <iostream>
using namespace std;

int N, M;
int ans[9];
bool visited[9];

void func(int x) {	// 현재 x개 까지의 수를 선택했다
	if (x == M) {	// m개 모두 선택했으면
		for (int i = 0; i < M; i++) {
			cout << ans[i] << " ";	// ans에 기록해둔 수를 출력한다.
		}
		cout << "\n";
	}
    
	else {
		for (int i = 1; i <= N; i++) {	// 1~N 까지 수에 대해서
			if (!visited[i]) {		// i가 아직 선택 안됬다면
            			// x번째 수를 i로 정하고
            			ans[x] = i;		
                        	// i를 선택했다고 visited 배열에 표시한다
				visited[i] = 1;		
                		// 다음 수를 정하기위해서 한번 더 func 호출
				func(x + 1);		
                		// x번째 수를 i로 정한 모든 경우에 대해서 확인했으니
                       	 	// i를 사용하지 않았다고 표시한다.
				visited[i] = 0;		
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
	cin >> N >> M;
	func(0);
}