반응형
CASE 1) 순서 O, 중복 X
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[9];
int ch[9];
void dfs(int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=1; i<=N; i++){
if(ch[i] == 0){
ch[i] = 1;
arr[depth] = i;
dfs(depth + 1);
ch[i] = 0;
}
}
}
}
int main(void) {
cin >> N >> M;
dfs(0);
return 0;
}
- check 배열과 arr 배열, 그리고 depth 를 사용하여 구현하였다.
CASE 2) 순서 X, 중복 X
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int ch[9];
int arr[9];
void dfs(int s, int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=s; i<=N; i++){
if(ch[i] == 0){
ch[i] = 1;
arr[depth] = i;
dfs(i, depth+1);
ch[i] = 0;
}
}
}
}
int main(void) {
cin >> N >> M;
dfs(1, 0);
return 0;
}
CASE 3) 순서 O, 중복 O
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[10];
void dfs(int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=1; i<=N; i++){
arr[depth] = i;
dfs(depth+1);
}
}
}
int main(void) {
cin >> N >> M;
dfs(0);
return 0;
}
CASE 4) 순서 X, 중복 O
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[10];
void dfs(int s, int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=s; i<=N; i++){
arr[depth] = i;
dfs(i, depth+1);
}
}
}
int main(void) {
cin >> N >> M;
dfs(1, 0);
return 0;
}
< 결론 >
순서 X - 0부터 시작
순서 O - s 부터 시작
중복 X - ch 배열 안씀
중복 O - ch 배열 씀
반응형
'Programming > Coding Test' 카테고리의 다른 글
9. C++ String 문법 정리 (0) | 2021.01.05 |
---|---|
8. 동적계획법 (0) | 2021.01.02 |
6. DFS - 부분집합 (0) | 2020.12.31 |
5. STL 정리 (0) | 2020.12.29 |
[C++] 백준 2573 빙산 - 테스트 케이스 (0) | 2020.11.15 |