DFS(깊이우선탐색)이란, y축(수직)방향을 먼저 탐색하는 알고리즘을 말하는 것으로서, 보통 재귀(Recursion)와 비슷한 형태를 하고 있다.
DFS를 통해 최소 항공권 비용을 구해보도록 할 것이다. 기본적으로, 모든 경로를 탐색하여 각 경로별로 나온 비용의 합을 비교해보도록 하여, 비용이 가장 작은 것을 출력해볼 것이다
위와 같은 그래프가 있을 때, 원 안의 숫자는 국가를, 화살표 위의 붉은 글씨는 비용을 뜻한다.
0국에서 1국으로 가는 경로 중 '최소 비용으로 갈 수 있는 경로'와 '비용'을 출력해보도록 하겠다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int n;
int val;
};
vector<vector<Node>> alist(5);
int used[5] = { 0 };
int cnt = 0; //경로 갯수
int sum = 0, arrSum[10], t = 0; //경로별 비용
void run(int now, int sum) {
if (now == 1) {
cnt++;
arrSum[t++] = sum;
}
for (int i = 0; i < alist[now].size(); i++) {
Node next = alist[now][i];
if (used[next.n] == 1) continue;
used[next.n] = 1;
run(next.n, sum + next.val);
used[next.n] = 0;
}
}
int main() {
// 비행기 노선, 비용 하드코딩
alist[0].push_back({ 1,6 });
alist[0].push_back({ 2,2 });
alist[0].push_back({ 4,2 });
alist[1].push_back({ 3,3 });
alist[2].push_back({ 1,5 });
alist[2].push_back({ 3,2 });
alist[3].push_back({ 1,1 });
alist[4].push_back({ 3,4 });
alist[4].push_back({ 2,6 });
run(0,0);
cout << "0국가 → 1국가로 갈 수 있는 경로별 비용: ";
for (int i = 0; i < cnt; i++) {
if (i == cnt-1) cout << arrSum[i];
else cout << arrSum[i] << ",";
};
cout << '\n';
int min = arrSum[0];
for (int i = 0; i < cnt; i++) {
if (arrSum[i] < min) {
min = arrSum[i];
}
}
cout << "0국가 → 1국가로 갈 수 있는 최소 비용: " << min << '\n';
cout << "경로 갯수: " << cnt << '\n';
return 0;
}
세상에...이런 방법이!!!