순열 알고리즘
네장의 카드를 모두 이용하여 숫자를 출력하고자 한다.
중복을 허용하지 않는 순열을 처리하는 방법
순열 알고리즘 규칙 1
재귀호출을 돌리지 않고, 다음과 같은 규칙으로 구할 수 있다.
1.
맨 오른쪽 부터 숫자부터 2개씩 비교한다.
2.
왼쪽보다 오른쪽 숫자가 더 큰 index를 찾아서 빨간색으로 체크한다.
3.
예를 들어서 1 6 5 3 이라면 1 6 5 3
4.
예를 들어서 5 6 17 이라면 5 6 1 7
5.
예를 들어서 7 8 1 1 이라면 7 8 1 1
이렇게 찾은 index를 a라고 하자.
순열 알고리즘 규칙 2
1.
다시 맨 오른 쪽 숫자부터 a까지 숫자를 찾자.
2.
[a]보다 더 큰 숫자를 발견하면 파란색으로 표시하자
3.
빨간색과 파란색 index값을 찾아내서 swap해주자
4.
예를 들어서 1 6 5 3 이라면 1 6 5 3 : 3 6 5 1
5.
예를 들어서 5 6 17 이라면 5 6 1 7 : 5 6 7 1
6.
예를 들어서 7 8 1 1 이라면 7 8 1 1 : 8 7 1 1
순열 알고리즘 규칙3
1.
a index 다음 숫자부터 맨 끝까지 숫자를 전부 뒤집음
2.
만약에 a뒤에 숫자가 3개있으면 3개다 뒤집음
3.
예를 들어서 1 6 5 3 이라면 1 6 5 3 : 3 6 5 1 → 3 1 5 6
4.
예를 들어서 5 6 17 이라면 5 6 1 7 : 5 6 7 1 → 5 6 7 1
5.
예를 들어서 7 8 1 1 이라면 7 8 1 1 : 8 7 1 1 → 8 1 1 7
#include <iostream>
char history[5] = "";
char cards[5] = "1234";
int visited[10] = { };
void dfs(int level)
{
if (level == 4)
{
std::cout << history << std::endl;
return;
}
for (int i = 0; i < 4; i++)
{
if (visited[i] == 0)
{
history[level] = cards[i];
visited[i] = 1;
dfs(level + 1);
visited[i] = 0;
history[level] = 0;
}
}
}
// 재귀함수를 쓰지않고 모든 순열을 출력하는 소스코드
int nextPermutation(int* data, int n)
{
// 오른쪽 왼쪽으로 a찾기 (index)
int i = n - 1;
while (i > 0 && data[i - 1] >= data[i]) i -= 1;
if (i <= 0) return 0;
// 오른쪽에서 왼쪽으로 b찾기 (index)
int j = n - 1;
while (data[j] <= data[i - 1]) j -= 1;
// swap data[i-1] and data[j]
int temp = data[i - 1];
data[i - 1] = data[j];
data[j] = temp;
//a값 이후의 위치부터 전부 뒤집기
j = n - 1;
while (i < j)
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
i += 1;
j -= 1;
}
return 1;
}
int main()
{
dfs(0);
std::cout << "===========nextPermutation===========" << std::endl;
int data[4] = { 1,2,3,4 };
int x;
int n = 4;
int result;
while (true)
{
for (x = 0; x< 4; x++)
{
std::cout << data[x];
}
std::cout << std::endl;
result = nextPermutation(data, n);
if (result == 0)
break;
}
return 0;
}
JavaScript
복사
그래프 DFS
DFS 그래프 경로찾기
A에서 D로가는 경로 총 네가지 경로가 있다.
A-B-D
A-B-C-D
A-C-D
A-C-B-D
기존 TREE DFS와 크게 다르지 않다.
프로토 타입 void dfs(int level, int now)
return 조건이 name[now] == ‘D’ 리턴
그래프니까 사이클생길수 있다. 무한재귀가 발생하지 않도록
싸이클 중복여부를 체크해줘야한다.
#include <iostream>
char name[5] = "ABCD";
int data[4][4] =
{
0,1,1,0,
1,0,1,1,
1,1,0,1,
0,1,1,0,
};
char history[5] = "";
int count = 0;
int IsPossible(int level, int select)
{
for (int i = 0; i < level; i++)
{
if (history[i] == name[select])
{
return 0;
}
}
return 1;
}
void dfs(int level, int now)
{
if (name[now] == 'D')
{
count++;
std::cout << history << std::endl;
return;
}
for (int i = 0; i < 4; i++)
{
if (data[now][i] == 1)
{
if (IsPossible(level, i) == 1)
{
history[level + 1] = name[i];
dfs(level + 1, i);
history[level + 1] = 0;
}
}
}
}
int main()
{
history[0] = name[0];
dfs(0, 0);
return 0;
}
JavaScript
복사
가중치 있는 그래프 탐색
A에서 D까지 가는 최소비용 Rounte찾는다.
인접행렬에서 0과 1대신에 가중치값을 넣어주고
전달인자에 sum 변수를 추가하여 누적합을 계산해준다.
진입할때 sum을더하고 다음 시점으로 이동한다.
#include <iostream>
char name[5] = "ABCD";
int data[4][4] =
{
0,10,60,0,
10,0,20,40,
60,20,0,50,
0,40,50,0,
};
char history[5] = "";
int count = 0;
int IsPossible(int level, int select)
{
for (int i = 0; i < level; i++)
{
if (history[i] == name[select])
{
return 0;
}
}
return 1;
}
void dfs(int level, int now, int sum)
{
if (name[now] == 'D')
{
count++;
std::cout << history << std::endl;
return;
}
for (int i = 0; i < 4; i++)
{
if (data[now][i] > 1)
{
if (IsPossible(level, i) == 1)
{
history[level + 1] = name[i];
dfs(level + 1, i, sum + data[now][i]);
history[level + 1] = 0;
}
}
}
}
int main()
{
history[0] = name[0];
dfs(0, 0, 0);
return 0;
}
JavaScript
복사
