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

문제

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

 

문제 이해

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구한다.

 

문제 풀이

💡DFS를 이용한 백트래킹

    1부터 N까지 재귀함수를 이용해 탐색하며 중복 없이 M개의 수를 선택하고 출력한다.

1. 종료 조건
   : M개의 수를 모두 선택했을 때
2. 탐색
   - 1부터 N까지 탐색을 반복한다.
   - 수를 중복해서 선택하지 않도록 방문 표기한다.
   - 탐색한 수를 출력할 배열에 삽입한다.
   - 탐색이 끝난 수를 배열에서 제거하고 방문하지 않은 수로 표기한다.
3. 탐색 종료
   - 선택한 M개의 수가 담긴 배열을 출력 후 탐색을 종료한다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

int N, M;
vector<int> v;
vector<bool> visited;

void dfs(int cur) {
    // 종료 조건: M개의 수를 모두 선택함
    if (cur == M) {
        for (int i: v)
            cout << i << ' ';
        cout << '\n';
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            v.push_back(i);

            dfs(cur + 1);

            visited[i] = false;
            v.pop_back();
        }
    }
}

int main() {
    cin >> N >> M;
    visited.assign(N + 1, false);

    dfs(0);

    return 0;
}