백준: N과 M

문제

• https://www.acmicpc.net/problem/15649
• 백트래킹

설명

• 1부터 N까지의 카드 중에서 M개를 뽑는 경우의 수를 구하라!
• 단, 순서가 있음을 주의
  • 즉, 1 4와 4 1은 다른 것으로 취급

알고리즘

• n_array, used_n 선언
  • 첫 번째 변수는 출력할 수를 담기 위한 벡터[길이 = M]
  • 두 번째 변수는 이 수를 방문 했는가?를 확인하기 위한 벡터[길이 = N]
• dfs(depth) 시작[depth 초기값 = 0]
  • 만약 depth == M이라면
    • n_array에 있는 내용을 출력하고 리턴
  • 아니라면
    • i = 0; i < n; i++ 반복문 실행
      • 만약 탐방하지 않은 수가 있다면
        • 해당 수를 탐방했다고 표시하고 dfs(depth+1) 실행
        • 실행 후 탐방을 하지 '않았다고' 표시함[왜냐: 순서가 있기 때문!]

  코드

#include <vector>
#include <cstdio>

using namespace std;

vector<bool> used_n;
vector<int> n_array;

int n, depth;

void dfs(int cur_depth) {
    if (cur_depth == depth) {
        for (int tmp : n_array) {
            printf("%d ", tmp);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!used_n[i]) {
            used_n[i] = true;
            n_array[cur_depth] = i+1;
            dfs(cur_depth + 1);
            used_n[i] = false;
        }
    }
}

int main(void) {
    scanf("%d %d", &n, &depth);

    // Resize Used
    used_n.resize(n, false);

    // Init Vector
    n_array.resize(depth, 0);

    dfs(0);
    return 0;
}