[Algorithm] DFS로 최소 항공권 비용 구하기

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;
}