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

 📚 문제

[BOJ C++] 백준 15650번: N과 M (2)
https://www.acmicpc.net/problem/15650

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• N과 M 시리즈는 조건에 만족하는 수열을 모두 출력하는 문제이다. 확률과 통계에서 배우는 순열, 조합, 중복순열, 중복조합을 구현한다고 생각하면 된다.
• 이번 N과 M (2)는 중복없이 1~N의 숫자로 오름차순이면서도 길이가 M인 수열을 만드는 문제이다. N과 M (1) 문제에 조건을 조금만 추가하면 쉽게 해결할 수 있다.
• [BOJ C++] 백준 15649번: N과 M (1)
• 재귀함수(DFS)와 백트래킹 방식을 사용하여 구현한다. 자세한 구현 방법은 다음과 같다.

 

•  방문 여부를 체크하는 배열(visited)과 선택한 값을 저장하는 배열(arr)을 준비한다. 선택한 숫자와 배열의 인덱스를 통일하기 위해 visited[0]은 사용하지 않고 길이를 N+1로 설정하였다. visited[i]는 숫자 i를 선택했는지의 여부를, arr[dep]는 배열의 (dep+1)번째에 삽입될 숫자를 저장한다.

 

• 반복문을 통해 1부터 N까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 없으므로 현재 숫자가 이미 방문한 숫자가 아닌 경우에만 선택할 수 있다. 또, 오름차순을 만족해야하므로 배열에 이미 저장되어있는 수보다 큰 수만 저장할 수 있다. 따라서 i가 arr[dep -1]보다 크며 방문한 적이 없는 숫자라면 visited[i]에 방문 표시를 하고 arr[dep]에 숫자 i를 추가한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.
• 함수가 return된 후에는 다시 해당 숫자를 비방문 처리한다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> visited(9);
vector<int> arr(9);

void dfs(int dep) {
    if (dep == m) {
        for (int i = 0; i < m; i++) cout << arr[i] << " ";
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && (!dep || (dep && i > arr[dep - 1]))) {
            visited[i] = 1;
            arr[dep] = i;
            dfs(dep + 1);
            visited[i] = 0;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    dfs(0);
}