[Baekjoon/C++] 15654: N과 M (5)

N과 M (5)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

해결

주어진 N과 M을 저장할 변수, 입력받은 N개의 숫자를 저장할 배열 arr, 선택된 M개의 숫자를 저장할 배열 res, 해당 숫자가 이미 선택되었는지 확인하기 위한 배열 visited 이렇게 사용할 변수들을 선언한다.

main함수에서는 N과 M을 입력받고 N개의 숫자를 입력받아 arr 배열에 저장한다.

입력받은 숫자를 sort 함수를 통해 오름차순으로 정렬하여 수열을 사전 순으로 증가하는 순서로 출력할 수 있도록 한다.

dfs 함수는 깊이 우선 탐색 알고리즘을 이용해 M개의 숫자를 선택하는 모든 경우의 수를 찾는다. 이 함수는 재귀적으로 호출되고 매번 선택된 숫자의 개수 cnt를 1 증가시키고 해당 숫자를 res 배열에 저장한다. cnt와 M과 같아질 시 선택된 숫자를 출력한다.

visited 배열을 통해 이미 선택된 숫자는 다시 선택되지 않도록 한다. 배열의 각 요소는 해당 인덱스의 숫자가 이미 선택되었는지를 나타내는 불리언 값이며 숫자를 선택할 때마다 해당 숫자의 visited 값을 true로 설정하고 선택을 취소할 때는 false로 설정한다.

---

정답

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n, m;
int arr[MAX];
int res[MAX];
bool visited[MAX];

void dfs(int cnt) {
    if(cnt == m) {
        for(int i = 0; i < m; i++) {
            cout << res[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            visited[i] = true;
            res[cnt] = arr[i];
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);  
    dfs(0);
    return 0;
}

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