#include <iostream>
#define MAX 9
using namespace std;
int n, m;
int arr[MAX];
bool visited[MAX + 1];
void dfs(int depth) {
if (depth == m) { // 리프 노드까지 방문했으면 출력
for (int i = 0; i < m; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 방문한 노드 가지 않음
visited[i] = true; // 방문 체크
arr[depth] = i;
dfs(depth + 1);
visited[i] = false; // dfs 완료 후 방문 해제
}
}
}
int main() {
cin >> n >> m;
dfs(0);
return 0;
}
중복 없이 M개를 고른 수열을 출력하는 순열 문제
= 서로 다른 n개에서 r개를 순서대로 고르는 순열 (즉, nPr
)
백트래킹
으로 주로 사용하는 DFS
를 사용하여 풀었다.
처음 뻗어나가는 노드를 보면
1. 방문하지 않았으면 숫자를 배열에 추가
2. depth를 증가하여 다음 위치로 커서 이동
3. depth가 끝까지 도달한 경우 출력 및 해당 dfs 함수 종료
4. 1 ~ 3번 반복
순열은 값의 중복 없이 줄 세우는 작업이다.