DevelopBeakjoon경우의 수

백준 15649 - N 과 M (1) - 순열

백준 15649 - N 과 M (1)

링크

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

문제 풀이

주어진 N 개에서 M 개를 뽑아 나열하는 순열 문제.

백트래킹 을 이용해 만들 수 있는 모든 수열의 경우의 수 를 만들어 준다. check 를 이용해 똑같은 숫자를 여러 번 뽑는 중복 행위를 판단하고 v 배열을 통해 한 수열이 만들어지면 출력하도록 한다.

  • v : 뽑은 숫자를 저장하기 위한 배열
  • check : 해당 숫자가 뽑혔는지 판단하기 위한 배열

전체 소스 코드

#include <iostream>
#include <vector>

#define endl '\n'
using namespace std;

vector<int> v;
vector<bool> check;

void dfs(int n, int m, int depth) {
    if (m == depth) {
        for (int value : v) {
            cout << value << " ";
        }
        cout << endl;
        return;
    }

    for (int i = 0; i < n; i++) {
        if (check[i] == true) {
            continue;
        }

        check[i] = true;
        v[depth] = i + 1;
        dfs(n, m, depth + 1);
        check[i] = false;
    }
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    v = vector<int>(M);
    check = vector<bool>(N);

    dfs(N, M, 0);
}
Share