BOJ/백준 - 15649 N과 M (1) C++

백트래킹 문제이다. 복습할겸 다시 풀어본 문제.

정답 비율이 60%라 풀어봤는데,, 처음 풀었을 때는 어려웠었던 기억이 있다.

다시 풀어보니까 확실히 뭔지 알 것 같았던 문제.

 

 

길이 M까지 cnt가 올라가면 arr에 있는 수 출력,

그게 아니라면 N까지 증가시켜주면서 dfs를 호출한다.

중복되는 수열을 여러번 출력하면 안된다고 했으니까 visit배열에 방문 여부를 표시해준다.

 

#include <iostream>
#define MAX 9
 
using namespace std;
 
int arr[MAX];
bool visit[MAX];
 
int N, M;
 
void dfs(int cnt) {
    if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << arr[i] << ' ';
        }
        cout << '\n';
    }
 
    for (int i = 1; i <= N; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            arr[cnt] = i;
            dfs(cnt+1);
            visit[i] = 0;
        }
    }
}
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> N >> M;
    
    dfs(0);
 
    return 0;
}