[15649] N과 M (1)

[15649] N과 M (1)

문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX 8

/* 변수 */
int N, M, output[MAX];
bool visited[MAX];

/* 함수 */
void tracker(int count) { // DFS하는 함수, count번째 과정임을 의미
    if(count == M) { // M만큼 output에 들어가면 출력 후 return
        for(int i = 0; i < M; i++) {
            cout << output[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for(int i = 0; i < N; i++) {
        if(!visited[i]) {
            visited[i] = true; // DFS처럼 visited true
            output[count] = i + 1; // 1부터 시작이기 때문에 i+1
            tracker(count + 1); // 다음 과정 실행
            visited[i] = false; // 돌아가기 전에 visited false
        }
    }
}

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

    /* 입력 */
    cin >> N >> M;

    /* 풀이 */
    tracker(0);

    /* 출력 */

}

부가 설명

백트래킹이 익숙하지 않아 꽤나 오래 걸린 문제이다.
여기저기 찾아보다가 DFS가 비슷한 개념인 것 같아 빌려왔다.
visited 배열을 만들어 방문여부에 따라 count해가며 output을 채워 M만큼 채우면 출력하고 돌아가는 것을 반복하며 다른 경우를 트래킹 한다.

출처 : https://www.acmicpc.net/problem/15649