[백준/C++] 15664번 N과 M (10)

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

15664번: N과 M (10)

 

문제분석

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하라!

조건 1. N개의 자연수 중에서 M개를 고른 수열

조건 2. 비내림차순 -> 길이가 K인 수열 A가 A1​≤A2​≤...≤Ak−1​≤Ak​​ 를 만족해야 한다.

- 입력으로는 첫째 줄에 N과 M이 주어진다. (1≤M,N≤8)​

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

- 출력으로는 한 줄에 하나씩 수열을 출력하며, 중복되는 수열을 여러 번 출력할 수 없다.

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

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int arr[8];
vector<int> v;
bool visited[8] = { 0, };

// dfs로 순열 구하기
void dfs(int idx, int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }
    int tmp = 0;
    for (int i = idx; i < v.size(); i++) {
        if (!visited[i] && v[i]!=tmp) {
            visited[i] = true;
            arr[cnt] = v[i];
            tmp = arr[cnt];
            dfs(i,cnt + 1);
            visited[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    v.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    dfs(0,0);
    return 0;
}

 

문제풀이

1. N과 M 그리고 N개의 숫자들을 차례로 입력받는다.

2. N개의 숫자는 벡터에 담아 오름차순으로 정렬한다.

3. dfs 함수를 실행하는데, 위치를 가리킬 idx변수와 횟수를 담을 cnt변수 2개가 필요하기 때문에 파라미터로 우선 0,0을 넘겨준다.

4. cnt값이 m, 즉 출력하고자 하는 수열의 길이에 도달하면 배열에 담긴 값들을 출력하고 return 한다.

5. 만약 아직 도달하지 못했다면, idx부터 백터 v의 길이만큼 for문을 돈다.

6. 현재 i가 가리키는 곳이 방문하지 않은 곳이고, tmp에 담긴 값과 동일하지 않다면(이전에 방문한 값과 다르다면 == 중복방지를 위해) 방문여부를 true로 변경한 후( 1 1, 7 7, 9 9처럼 자기 자신을 다시 탐색하는 것을 방지하기 위해) 백터v에 담긴 값을 배열 arr에 넣고 tmp에도 넣어준다.

7. 그리고 dfs를 현재 위치를 가리키는 i값과 cnt에 +1 된 값을 인자로하여 호출한다. 후에 호출이 끝나면(벡터 v에 담긴 하나의 값에 대한 dfs가 끝나면) 방문여부를 false로 초기화해주고(why? 다음 값에 대해 다시 탐색해야하기 때문) for문에 의해 i를 ++해준다. (다음 벡터 값으로 이동)