문제

15649번: N과 M (1)

풀이

#include <iostream>

using namespace std;

// * 문제: 1부터 N까지 자연수 중에서, 중복 없이 M개를 고른 수열

// - dfs 함수 내부에서, 현재 보고 있는 자릿수에 어떤 숫자를 넣을 것인지를 탐색
// - 다음 자릿수(dfs 함수)로 넘어갈 때, 방문처리 되지 않은 숫자에 대해서만 탐색 이어가기

int n, m;
bool visited[9]; // 1 ~ n 까지의 숫자가 수열에 포함되어 있는지 저장하는 배열
int result[9]; // 각 경우에서 완성된 m자릿수 수열을 저장하는 배열

void dfs(int cnt) { // cnt -> 지금까지 형성된 수열의 자릿수
    if (cnt == m) { // m 자릿수 수열이 완성되었다면, 해당 수열을 출력 후 함수 종료
        for (int i = 0; i < m; ++i) {
            cout << result[i] << ' ';
        }
        cout << '\\n';
        return ;
    }
	
		// 다음 자릿수에 넣을 숫자 선택하기
    for (int i = 1; i <= n; ++i) {
        // 수열에 아직 i가 포함되지 않은 상태라면,
        if (!visited[i]) {
            visited[i] = true; // 해당 수열에 i가 중복되지 않도록, 방문 처리 표시하기
            result[cnt] = i; // 현재 자릿수를 i로 설정하기
            dfs(cnt + 1); // 다음 자릿수 탐색하기
            visited[i] = false; // 그 다음 수열을 탐색하기 위해 i에 대한 방문 처리 해제하기
            result[cnt] = 0; // 다음 수열을 만들기 위해, 현재 자릿수를 지우기
        }
    }
}

int main() {
    cin >> n >> m;

    dfs(0); // 0 자릿수부터 시작

    return 0;
}