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

소스코드

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int arr[8];
int selected[8];
int N, M;

void recur(int selCnt, int idx){
	if (idx == N+1) return;
	if (selCnt == M){
		for(int j = 0; j < selCnt; j++){
			cout << selected[j] << " ";
		}
		cout << "\n";
		return;
	}
	for(int i = idx; i<N; i++){
		selected[selCnt] = arr[i];
		recur(selCnt+1, i+1);
	}
}
int main(){
	cin >> N >> M;

	for (int i=0; i<N; i++){
		arr[i] = i+1;
	}

	recur(0,0);	 
}

backtracking을 이용해 탐색하는 문제이다. 

해설

함수 부분만 따로 살펴보자. 

main함수에서는 N, M을 입력받고, arr에 1부터 N까지의 자연수들을 넣어준 후에 recur함수를 호출한다.

 

void recur(int selCnt, int idx){
	if (idx == N+1) return;
	if (selCnt == M){
		for(int j = 0; j < selCnt; j++){
			cout << selected[j] << " ";
		}
		cout << "\n";
		return;
	}
	for(int i = idx; i<N; i++){
		selected[selCnt] = arr[i];
		recur(selCnt+1, i+1);
	}
}

 

backtracking 함수를 작성 (재귀함수) 하여 해결하였다.

idx가 N+1이면 종료해 준다. (base state 1) (EX. N이 4일 경우, N+1일 때, 즉 5일 때 retrun해야 한다.) 

selCnt가 M이면, 이 state가 정답인 state이므로 selected 안에 있는 내용물을 for문을 이용해 출력해 준다. 그리고 return으로 되돌려보내기.

이 두 가지를 통해 재귀함수가 종료될 수 있는 분기점을 만들었다. 그 아래쪽은 다음 함수와 연결하는 부분이다.

한 node에서 다음 node로 갈 때, 나 자신을 제외한 모든 arr의 다른 node로 이어질 수 있으므로 for문을 이용해 idx부터 N까지의 원소를 selcted에 저장해준다. 그리고 나서 recur(selCnt+1, i+1) 로 index를 하나 채우고 selCnt를 하나 채운 경우로 다시 함수를 호출하여 함수가 반복 진행되도록 한다.