Baekjoon 15649 N과 M (1)

Baekjoon 15649 N M (1)

• 최초 작성일: 2021년 10월 01일(금)
• 주소: https://www.acmicpc.net/problem/15649

##

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

##

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

##

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

##

• 백트래킹

##

• 백트래킹이란, 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾는 기법을 말한다.
• 다시 말해, 굳이 확인 안해도 되면 안한다는 거다.
• 그래서 dfs를 구현하되, 조건을 넣어 굳이 안 해도되는건 제외시켜주는거다.
• bool 형태의 visited 배열을 선언해준다. ( 1 ≤ M ≤ N ≤ 8 이라고 했으니 여유롭게 9개 줬다.)
• visited가 true면 이미 쓴 것으로, continue로 과정을 생략한다. false라면, true로 미리 바꿔주고 다음 숫자부터 dfs를 반복한다. 반복을 시작하기 전 다시 visited를 안 쓴 것으로 해줘야하므로 false로 변경해준다.

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

// 1 ~ n 까지 자연수 중 중복 없이 m개를 고른 수열

int n, m;
int arr[9];
bool visited[9];

void print() {
    for (int i = 0; i < m; i++) cout << arr[i] << " ";
    cout << "\n";
}

void dfs(int cnt) {
    while(cnt == m) {
        print();
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (visited[i] == true) continue;
        arr[cnt] = i;
        visited[i] = true;
        dfs(cnt + 1);
        visited[i] = false; 
    }
}

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

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

    return 0;
}