알고리즘/그리디&완탐
[백트래킹]끝점을 늘려가면서 탐색하는 순열조합+a
안잡아모찌
2019. 8. 11. 13:55
순서를 하나씩 늘려가면서 완전탐색을 진행해야하는 경우, 끝점을 포문으로 돌려서 if절을 구현.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#include <vector>
using namespace std;
struct INFO {
bool isV = false;
};
INFO info[5];
int isV[5];
vector<int> v;
//EndPoint를 늘려주면서 dfs탐색
void dfs(int s,int len,int ep) {
if (len == ep) {
for (int i = 0; i < len; i++) {
printf("%d ", v[i]);
}
printf("\n");
return;
}
for (int i = s; i < 5; i++) {
if (isV[i] == false) {
isV[i] = true;
v.push_back(i);
dfs(i, len + 1,ep);
isV[i] = false;
v.pop_back();
}
}
}
int main()
{
for(int i=1;i<=5;i++) dfs(0,0,i);
return 0;
}
|
cs |
<정답을 찾은 경우 더이상 진행할 필요가 없는 경우>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <vector>
using namespace std;
int isV[5];
bool flag = false; //만약에 정답을 찾으면 재귀를 빠져나오기위한 플러그설정!
vector<int> v;
void dfs(int s,int len,int ep) {
if (len == ep) {
for (int i = 0; i < len; i++) {
printf("%d ", v[i]);
}
printf("\n");
if (len == 3) flag = true; //만약 답을 찾은경우. 뒤에꺼를 실행안되게 하기위해서.
return;
}
for (int i = s; i < 5; i++) {
if (isV[i] == false && flag==false) { //플러그가 true로바뀌면 실행안되도록.
isV[i] = true;
v.push_back(i);
dfs(i, len + 1,ep);
isV[i] = false;
v.pop_back();
}
}
}
int main()
{
for(int i=1;i<=5;i++) if(flag==false) dfs(0,0,i);
return 0;
}
|
cs |
<X이상 이면 실행중지의 조건을 통해 Backtracking을 통한 모든 경우탐색>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> v;
bool isV[6];
void dfs(int len) {
for (int i = 0; i < v.size(); i++) {
printf("%d ", v[i]);
}printf("\n");
if (len == 3)return;
for (int i = 0; i < 6; i++) {
if (!isV[i]) {
isV[i] = true;
v.push_back(i);
dfs(len + 1);
v.pop_back();
isV[i] = false;
}
}
}
int main()
{
dfs(0);
return 0;
}
|
cs |
